首页 > 其他 > 详细

codevs 5059 一起去打CS

时间:2016-07-09 20:42:43      阅读:188      评论:0      收藏:0      [点我收藏+]
/*
空间32000 我写的全都31900+ 醉了
可以降维优化空间的 懒得写了
状态:f[i][j] 前i个题目a一共做了j分钟 b最少的做题时间 
转移:考虑每个题目给谁做  f[i][j] = min ( f[i-1][j-a]a做 , f[i-1][j]+b b做);
最后对于f[n]枚举a的做题时间 更新答案 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 201
using namespace std;
int n,a,b,sum,ans=0x3f3f3f3f,f[maxn][maxn*maxn];
int main()
{
    scanf("%d",&n);
    memset(f,127/3,sizeof(f));f[0][0]=0;
    for(int i=1;i<=n;i++)
      {
          scanf("%d%d",&a,&b);sum+=b;
        f[i][0]=sum;
        for(int j=0;j<=40000;j++)
          if(j>=a)f[i][j]=min(f[i-1][j-a],f[i-1][j]+b);
          else f[i][j]=f[i-1][j]+b;
      }
      
    for(int i=1;i<=40000;i++)
      ans=min(ans,max(i,f[n][i]));
    printf("%d\n",ans);
    return 0;
}

 

codevs 5059 一起去打CS

原文:http://www.cnblogs.com/yanlifneg/p/5656579.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!