zoj3682 背包
刚开始看这题，根本没想到是背包，看来对背包的理解还不够透彻
/*背包问题：1.因为题目中提到所有广场所能容纳的人数刚好等于总人数，所以只要 安排好其中一方粉丝（a），另一方就唯一确定了。2.取s=min(s1,s2)，则可以把s看做背包体积，每个广场所能容纳的人数看做 每个物品的体积3.每个广场有三种选择方式，全部放a，不放a，放一半a（前提是总数为偶数）*/#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int M=1000000007;int dp[100005],w[205];int main(){ int s1,s2,s,i,j,n; while(~scanf("%d%d",&s1,&s2)) { s=min(s1,s2); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",w+i); memset(dp,0,sizeof(dp)); dp[0]=1; for(i=1;i<=n;i++) for(j=s;j>=1;j--) { //此处注意dp[j]的值很容易超过int32，所以要每次%M if(w[i]%2==0&&j>=w[i]/2&&dp[j-w[i]/2]!=0) dp[j]=(dp[j]+dp[j-w[i]/2])%M; if(j>=w[i]&&dp[j-w[i]]!=0) dp[j]=(dp[j]+dp[j-w[i]])%M; } printf("%d\n",dp[s]); } return 0;}