Home > Old Blog Posts > USACO 3.1.2 Score Inflation

USACO 3.1.2 Score Inflation


一道典型的完全背包的题目

详细讲解可以参见dd_engi的背包九讲

我只简单地说一下

两重循环

外层循环物品,一个一个地装

内层循环是分值数

基本方程为f[j]=max(f[j],f[j-times[i]]+score[i]),状态的含义为用前i道题,总时间为j的最大值

此外这个dp还可以剪枝,在内层循环之前,判断若score[i]<=f[times[i]]可以直接跳过,用这个物品也是浪费

这个优化的力度比较大

代码:

/*
ID: dementr1
PROG: inflate
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“inflate.in”);
ofstream fout(“inflate.out”);
int M,N,score[10000]={},times[10000]={},f[10001]={};
void init()
{
int i;
fin>>M>>N;
for(i=0;i<N;i++)
fin>>score[i]>>times[i];
fin.close();
}
void work()
{
int i,j;
for(i=0;i<N;i++)
if(score[i]>f[times[i]])
for(j=0;j<=M;j++)
if(j-times[i]>=0)
f[j]=max(f[j],f[j-times[i]]+score[i]);
fout<<f[M]<<endl;
fout.close();
}
int main()
{
init();
work();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: