解题思路:
注意事项:
参考代码:
#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++代码)浏览:868 |
C语言程序设计教程(第三版)课后习题10.1 (Java代码)浏览:1447 |
A+B for Input-Output Practice (IV) (C++代码)浏览:678 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:485 |
简单的a+b (C语言代码)浏览:632 |
C语言程序设计教程(第三版)课后习题6.6 (C++代码)浏览:633 |
【绝对值排序】 (C语言代码)浏览:825 |
1048题解(读入回车问题)浏览:566 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:616 |
大神老白 (C语言代码)浏览:601 |