解题思路:
注意事项:
参考代码:
#include<bits/stdc++.h>//一维dp,思路是
//把每个砝码拆成一正一反两个质量,这样所有砝码都只需要放左边就行了。
using namespace std;
#define maxw 100010
#define maxn 110
int n;
int sum=0;
int a[maxn<<1];
int dp[maxw];
void init(){
memset(a,0,sizeof(a));
}
void debug(){
for(int i=1;i<=sum;i++){
printf("%d ",dp[i]);
}putchar('\n');
}
int main(){
init();
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
for(int i=n+1;i<=n*2;i++){
a[i]=-a[i-n];
}
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=sum;j>=0;j--){
if(dp[j]==1&&j+a[i]>0){
dp[j+a[i]]=1;
}
}
//debug();
}
for(int i=n+1;i<=2*n;i++){
for(int j=0;j<=sum;j++){
if(dp[j]==1&&j+a[i]>0){
dp[j+a[i]]=1;
}
}
//debug();
}
//debug();
int ans=0;
for(int i=1;i<=sum;i++){
if(dp[i])ans++;
}
printf("%d",ans);
return 0;
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:565 |
点我有惊喜!你懂得!浏览:4109 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:623 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:569 |
九宫重排 (C++代码)浏览:1336 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:775 |
C语言训练-求函数值 (C语言代码)浏览:580 |
C语言训练-大、小写问题 (C语言代码)浏览:732 |
【金明的预算方案】 (C++代码)浏览:940 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:591 |