Yiner的ACM

成长的痕迹
<2011年4月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

统计

  • 随笔 - 29
  • 文章 - 0
  • 评论 - 2
  • 引用 - 0

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

完全背包

/**********************************
有一定的钱 存在银行里
给出可存的钱数 和相应利息
第一年的利息会加入到第二年的本金中
***********************************/

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int d[50000],v[12],w[12];//数组开大了会超时
int main()
{

    int n;
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    for(int l=1;l<=n;l++)
    {
        int c,k;
        int m;
        scanf("%d %d",&c,&k);
        scanf("%d",&m);

        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&v[i],&w[i]);
            v[i]/=1000;
        }
        while(k--)
        {
             int t=c/1000;//因为是1000的倍数 所以 都除以1000 优化一下子
        memset(d,0,sizeof(d));
        for(int i=1;i<=m;i++)
         for(int j=0;j<=t;j++)
         {   if(j>=v[i])
             if(d[j]<(d[j-v[i]]+w[i]))
            {
                d[j]=d[j-v[i]]+w[i];
            }
        }
         c=c+d[t];
        }
         printf("%d\n",c);
    }
    return 0;
}

 

posted on 2011-04-08 11:33 Yiner 阅读(95) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理