求助
查看原帖
求助
1045061
2005citiwujie楼主2024/1/26 20:56

这种转移方程为啥不对?

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int INF=1<<30;
int n,ans;
int a[N],sum,dp[N][N];
signed main()
{
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    sum+=a[i];
  }
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=sum;j++)
    {
      if(j==a[i]) dp[i][j]=1;
      if(dp[i-1][j]==1) dp[i][j]=1;
      if(dp[i-1][j+a[i]]) dp[i][j]=1;
      if(dp[i-1][abs(j-a[i])]) dp[i][j]=1;
    }
  }
  for(int i=1;i<=sum;i++)
  {
    if(dp[n][i]) ans++;
  }
  cout<<ans<<"\n";
  return 0;
}
2024/1/26 20:56
加载中...