几个分组背包题 zoj 3450 hdu 4341 hdu 4345
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3450
http://acm.hdu.edu.cn/showproblem.php?pid=4345
http://acm.hdu.edu.cn/showproblem.php?pid=4341
zoj 3450 和 hdu 4341 是同样的题，- -！，真不知道多校审题是怎么审的
可以直接极角排序，对同一条线上的点处理一下，
即要么区第一个，要么取第一二两个。。。。
一条线就是一组物品，每组物品最多选一个，典型的分组背包，如果用一维数组的话要小心物品的体积为0的情况。
zoj 3450
这题极角排序的话好像中间计算结果会溢出，用double可能会有浮点误差，所以直接用数学方法做了
#include<cstdio>#include<cstring>#include<vector>#include<cmath>#include<algorithm>using namespace std;__int64 dp[1010];vector<int> edge[200];bool isp(int num){ for(int i=2;i<=sqrt(num*1.0);i++){ if(num%i==0) return false; } return true;}int main(){ int n; while(scanf("%d",&n)!=EOF){ int tot=0; for(int i=0;i<200;i++) edge[i].clear(); for(int i=2;i<1000;i++){ if(isp(i)){ for(int j=i;j<=1000;j*=i){ edge[tot].push_back(j); } tot++; } } for(int i=0;i<=n;i++) dp[i]=1; for(int i=0;i<tot;i++) for(int v=n;v>=0;v--) for(int j=0;j<edge[i].size()&&edge[i][j]<=v;j++) dp[v]+=dp[v-edge[i][j]]; printf("%I64d\n",dp[n]); } return 0;}