解题思路:
注意事项:
参考代码:
#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语言程序设计教程(第三版)课后习题6.11 (C语言代码)for循环浏览:1114 |
分糖果 (C++代码)浏览:1439 |
十->二进制转换 (C语言代码)浏览:1291 |
C语言程序设计教程(第三版)课后习题1.5 (C++代码)浏览:1080 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:678 |
WU-链表数据求和操作 (C++代码)浏览:1313 |
IP判断 (C语言代码)浏览:762 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:373 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:467 |
矩阵加法 (C语言代码)浏览:1720 |