题解 P2918 【[USACO08NOV]买干草Buying Hay】

CYMZ · 2019-01-22 17:34:04 · 题解

此题想讲讲优化。优化后，大部分测试用例提速>10倍。 dp[i]:花费为i时能买到的最大重量干草。 tp:干草重量>=h时，花费的当前最优值。 优化思路：

for(int j=c; j<tp; j++){ 
//每一次更新，上限是当前最优花费tp；
  dp[j] = max(dp[j], dp[j-c]+p);
  if(dp[j]>=h) {tp=j; break;}
  //如果发现满足要求的更优值，就更新tp,跳出循环
}

综上，最终结果就是tp，全部代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxc=500005;

int n, h, p, c, tp, dp[maxc];

int main(){
  while(scanf("%d%d", &n, &h)!=EOF){
    for(int i=0; i<maxc; i++)  dp[i]=0;
    tp = maxc;
    for(int i=1; i<=n; i++){
      scanf("%d%d", &p, &c);
      for(int j=c; j<tp; j++){
        dp[j] = max(dp[j], dp[j-c]+p);
        if(dp[j]>=h) {tp = j;  break;}
      }
    }
    printf("%d\n", tp);
  }
  return 0;
}