玄关
查看原帖
玄关
1292740
hanruize123楼主2024/11/1 21:15

为什么用一维dp就会挂啊!!
二维就过了

#include<bits/stdc++.h>
using namespace std;
int dp[200001],a[100001];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,v=0,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	//	dp[a[i]]=1;
		v+=a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=v;j>=1;j--){
			if(j==a[i]) dp[j]=1;
			else if(dp[j+a[i]]) dp[j]=1;
			else if(dp[abs(j-a[i])]) dp[j]=1;
		}
	//	for(int j=0;j<=v;j++) if(dp[j]) cout<<j<<" ";
	//	cout<<"\n";
	}
	for(int i=1;i<=v;i++){
		if(dp[i]){
			ans++;
		//	cout<<i<<" ";
		}
	}
	cout<<ans;
	return 0;
}
2024/11/1 21:15
加载中...