几个分组背包题 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;}