飞雪天涯 2011-10-16 21:18:00
点我顶贴
收藏
删除
终于AC了,5555555555555
我好不容易才找到真正求解背包问题第k优解的程序!
dp[0][1]=0;
for (int i=1;i<=n;i++){
int weight,value;
cin>>weight>>value;
for (int j=v;j>=weight;j--)
if (dp[j-weight][1]>=0){
int pos1=1,pos2=1;
for (int people=1;people<=k;people++){
queue1[people]=dp[j-weight][people]+value;//队列1
queue2[people]=dp[j][people];//队列2
if (queue2[pos1]>=queue1[pos2]) dp[j][people]=queue2[pos1++];
else dp[j][people]=queue1[pos2++];
//类归并排序方法
}
}
}
#4 libojie@2008-10-26 09:36:00
7596
回复
删除
若第N个AC的题恰好是第N号题,那么称这个题为AC的一个不动点。我们可以计算AC N个题,共M个题的情况下有P个不动点的概率。
这是一个数学问题,同时是一个信息学编程问题……
#5 cc@2008-10-26 16:16:00
7597
回复
删除
关于博弈中的ac是说 ,你ac了n个题,这n个题都是你懒得ac的 ,那么剩下的m个题中必然有p个题你仍然懒得ac,所以你还可以迅速ac掉…个题,这必然使rq下降,导致你能ac的题数目下降从而进一步导致noip的失利,所以,懒得ac的题多不一定是最优策略…… cc