首页 > 代码库 > noip前的dp挣扎
noip前的dp挣扎
写了几道比较水的dp，但是也有很多问题，初始化和循环的顺序等问题、还有最大的问题：动规方程。。。
CODEVS1253 超级市场
某人喜欢按照自己的规则去市场买菜，他每天都列一个买菜的清单，自由市场的菜码放也有一个顺序，该人有一个特点，就是按顺序买菜，从不走回头路，当然，她希望能花最好的钱买到所有的菜，你能帮帮他吗？
输入输出数据如下图：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;struct use{ int kind; double mon;}b[100001];double f[100001][101]={0};int a[101]={0};int main(){ int i,j,n,m,k; scanf("%d%d",&m,&n); memset(f,127,sizeof(f)); for (i=1;i<=m;++i) scanf("%d",&a[i]); for (i=1;i<=n;++i) scanf("%d%lf",&b[i].kind,&b[i].mon); for(i=1;i<=n;++i) f[i][0]=0; for (i=1;i<=n;++i) for (j=1;j<=m;++j) { f[i][j]=f[i-1][j]; if (b[i].kind==a[j]) f[i][j]=min(f[i][j],f[i-1][j-1]+b[i].mon); } if (f[n][m]>0x7fffffff) printf("Impossible\n"); else printf("%.2f\n",f[n][m]);}
CODEVS1959 拔河游戏
一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够）在其中的一组，要求两个组的人数相差不能超过1，且两个组内的所有人体重加起来尽可能地接近。
思路：一个二维费用（bool）背包问题，一个是元素个数（相当于体积），一个是体重。先求出总重的一半和元素个数一半，进行背包。
#include<iostream>#include<cstdio>using namespace std;bool f[101][45001]={false};int a[101]={0};int main(){ int i,j,sum=0,n,k,q,cha,summ; cin>>n; if (n%2==0) k=n/2; else k=n/2+1; for (i=1;i<=n;++i) { cin>>a[i]; sum+=a[i]; } if (summ%2==0) summ=sum/2; else summ=sum/2+1; for (i=0;i<=1;++i) f[i][0]=true; for (i=1;i<=n;++i) for (j=summ;j>=a[i];--j) for (q=k;q>=1;--q) f[q][j]=f[q][j]||f[q-1][j-a[i]]; for (j=summ;j>=0;--j) if (f[k][j]) { cout<<min(j,sum-j)<<" "<<max(j,sum-j)<<endl; break; } }
CODEVS1060 搞笑世界杯
随着世界杯小组赛的结束,法国,阿根廷等世界强队都纷纷被淘汰,让人心痛不已. 于是有
人组织了一场搞笑世界杯,将这些被淘汰的强队重新组织起来和世界杯一同比赛.你和你的朋
友欣然去购买球票.不过搞笑世界杯的球票出售方式也很特别,它们只准备了两种球票.A 类
票------免费球票 B 类票-------双倍价钱球票.购买时由工作人员通过掷硬币决定,投到正面
的买A类票, 反面的买B类票.并且由于是市场经济,主办方不可能倒贴钱,所以他们总是准备
了同样多的A类票和B类票.你和你的朋友十分幸运的排到了某场精彩比赛的最后两个位置.
这时工作人员开始通过硬币售票.不过更为幸运的是当工作人员到你们面前时他发现已无需
再掷硬币了,因为剩下的这两张票全是免费票。
你和你的朋友在欣喜之余,想计算一下排在队尾的两个人同时拿到一种票的概率是多少
(包括同时拿A 类票或B类票) 假设工作人员准备了2n 张球票,其中n 张A类票,n 张B类票,并且排在队伍中的人每人必须且只能买一张球票(不管掷到的是该买A 还是该买B).
思路：先说一个比较坑爹的事情，读入的是2n，不是n。f[i][j]表示第i人买票时买了j张A票的概率。对于j有三种情况：
1）j=0：f[i][j]=f[i-1][j]*0.5; 2)0<j<n:f[i][j]=(f[i-1][j]+f[i-1][j-1])*0.5; 3)j=n:f[i][j]=f[i-1][j]+f[i-1][j-1]*0.5。
初始化f[0][0]=1;输出f[n*2-2][n]*2(因为最后两张可以全是A或B);
#include<iostream>#include<cstdio>using namespace std;double f[3000][3000]={0};int main(){ int n,i,j; cin>>n; n/=2; f[0][0]=1; for (i=1;i<=2*n;++i) for (j=0;j<=n;++j) { if (j>i) continue; if (j==0) f[i][j]=f[i-1][j]*0.5; else { if (j<n) f[i][j]=(f[i-1][j]+f[i-1][j-1])*0.5; else f[i][j]=f[i-1][j]+f[i-1][j-1]*0.5; } } printf("%.4f\n",f[n*2-2][n]*2);}
CODEVS3369 膜拜
神牛有很多…当然…每个同学都有自己衷心膜拜的神牛.
某学校有两位神牛，神牛甲和神牛乙。新入学的N位同学们早已耳闻他们的神话。所以，已经衷心地膜拜其中一位了。
现在，老师要给他们分机房。
但是，要么保证整个机房都是同一位神牛的膜拜者，或者两个神牛的膜拜者人数差不超过M。
另外，现在N位同学排成一排，老师只会把连续一段的同学分进一个机房。老师想知道，至少需要多少个机房。
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;int f[3000]={0},sum1[3000]={0},sum2[3000]={0};int main(){ int n,m,i,j,x; memset(f,127/3,sizeof(f)); scanf("%d%d",&n,&m); for (i=1;i<=n;++i) { sum1[i]=sum1[i-1]; sum2[i]=sum2[i-1]; scanf("%d",&x); if (x==1) ++sum1[i]; else ++sum2[i]; } f[0]=0; for (i=1;i<=n;++i) for (j=0;j<i;++j) if (abs((sum1[i]-sum1[j])-(sum2[i]-sum2[j]))<=m|| sum1[i]-sum1[j]==0||sum2[i]-sum2[j]==0) f[i]=min(f[i],f[j]+1); cout<<f[n]<<endl;}
CODEVS
现在有n个物品（有可能相同），请您编程计算从中取k个有多少种不同的取法。
思路：多重背包问题，将数字作为元素，出现的次数为个数。注意选取个数时候的循环要循环到1，一开始循环到了0，结果wa了。。。作死。。。
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int a[31],f[31]={0},w[31]={0};int main(){ int n,k,i,j,p; cin>>n>>k; for (i=1;i<=n;++i) cin>>a[i]; sort(a+1,a+n+1); ++w[0]; ++w[w[0]]; for (i=2;i<=n;++i) { if (a[i]==a[i-1]) ++w[w[0]]; else { ++w[0]; ++w[w[0]]; } if (w[w[0]]>k) w[w[0]]=k; } f[0]=1; for (i=1;i<=w[0];++i) for (j=k;j>=0;--j) for (p=w[i];p>=1;--p) if (j>=p) f[j]=f[j]+f[j-p]; cout<<f[k]<<endl;}
noip前的dp挣扎