简单的动态规划

f:=max{f, f+a[i]}

medic数据输入换一下位置...

AC...

xmflsoi

厦门外国语oi?

.........不知道是谁

1104会做,这题也就不成问题了.

=medic的程序中输入部分改一下，其他…………原封不动…………怎么会这样的

还是经典问题0/1背包问题..汗...包了这样一层华丽的服装,到头来还是赤裸裸的背包问题...-_-!!

就是啊，这难道不是medic？我medic的全测试了遍通过，为什么这里不通过？~~55555555555555

和今年普及组的medic异曲同工

基本0-1背包

类似NOIP普及组采药

#include<stdio.h>
#define pr printf
#define sc scanf
int n,t,fi[105],ti[105],i,j,dp[1001];
int max(int a,int b)
{
if(a>b) return a;
else return b;
}
int main()
{
sc("%d%d",&n,&t);
for(i=1;i<=n;i++) sc("%d%d",&fi[i],&ti[i]);
for(i=1;i<=n;i++)
for(j=t;j>=ti[i];j--)
dp[j]=max(dp[j],dp[j-ti[i]]+fi[i]);
pr("%d",dp[t]);
return 0;
}

01背包 O（N*V） 空间O（V）
#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,t[101],f[101],dp[1001];

int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d%d",&f[i],&t[i]);
for (int i=1;i<=n;i++)
for (int v=m;v>=t[i];v--)
dp[v]=max(dp[v],dp[v-t[i]]+f[i]);
printf("%d",dp[m]);
return 0;
}

C++
http://www.cnblogs.com/937337156Zhang/p/6044241.html

// OpenJudgeTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#ifndef _DEBUG
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
#include <fstream>
#include <Windows.h>
#include <iterator>
#include <set>
#include <process.h>
#include <ctime>
#include <utility>
#include <cctype>
#include <bitset>
#include <stdarg.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?a:b)
#endif // _DEBUG

using namespace std;
int main() {

int n, t, value[101] = { 0 }, cost[101] = { 0 }, dp[1001] = { 0 };
cin >> n >> t;
for (int i = 1; i <= n; i++)
cin >> value[i] >> cost[i];
for (int i = 1; i <= n; i++)
for (int v = t; v >= cost[i]; v--)
dp[v] = max(dp[v], dp[v - cost[i]] + value[i]);

cout << dp[t];

#ifdef _DEBUG
system("pause");
#endif // _DEBUG
return 0;
}

var
num,time:integer;
i,j,max:integer;
f,t:array[0..1001] of integer;
opt:array[0..1001] of integer;

begin
read(num,time);
for i:=1 to num do
read(f[i],t[i]);

fillchar(opt,sizeof(opt),0);
for i:=1 to num do
for j:=time downto t[i] do
if opt[j-t[i]]+f[i]>opt[j]
then opt[j]:=opt[j-t[i]]+f[i];

max:=-maxint;
for i:=1 to time do
if opt[i]>max then max:=opt[i];
writeln(max);
end.

QWQ蒟蒻的01背包

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100+5;
const int maxt=1000+5;
const int maxf=10000+5;
int d[maxt][maxf],f[maxn],time[maxn];
int main(){
int n,t;
scanf("%d%d",&n,&t);
for(int i=1;i<=n;i++)
scanf("%d%d",&f[i],&time[i]);
for(int i=n;i>=1;i--)
for(int j=0;j<=t;j++){
d[i][j]=(i==n?0:d[i+1][j]);
if(j>=time[i]) d[i][j]=max(d[i][j],d[i+1][j-time[i]]+f[i]);
}
printf("%d",d[1][t]);
return 0;
}


弄了半天发现是输入反了。NO EXPLAINATION。
```
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
//f[i][x] = max(f[i - 1][x], f[i - 1][x - W[i] + C[i]])
int f[110][1100];
int m;
int t;
int W[110];
int C[110];

int big(int x, int y)
{
if (x > y)
return x;
else
return y;
}

int main()
{
//freopen("a.in", "r", stdin);
cin>>m>>t;
int i, j;
for (i = 1; i <= m; i++){cin>>C[i]>>W[i];}

for (i = 1; i <= m; i++)
for (j = 1; j <= t; j++)
{
if (j >= W[i])
{
f[i][j] = big(f[i - 1][j], f[i - 1][j - W[i]] + C[i]);
}
else
{
f[i][j] = f[i - 1][j];
}
}
cout<<f[m][t];
return 0;
}

01背包问题 不解释
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define N 1005
typedef long long ll;
using namespace std;
int main()
{
int n,t;
int a[N],b[N];
int dp[N];
scanf("%d",&n);
scanf("%d",&t);
memset(dp,0,sizeof(dp));
int i,j;
for(i=0;i<n;i++)
scanf("%d%d",&a[i],&b[i]);
for(i=0;i<n;i++)
{
for(j=t;j>=b[i];j--)
{
dp[j]=max(dp[j],dp[j-b[i]]+a[i]);
}
}
printf("%d\n",dp[t]);

}

极简pascal满分程序：
var a:array[0..1000]of longint;
n,m,o,x,y,i:longint;
Begin
readln(n);
readln(m);
for o:=1 to n do
begin
readln(x,y);
for i:=m downto y do
if a[i]<a[i-y]+x then a[i]:=a[i-y]+x;
end;
write(a[m]);
end.

好简单01背包啊。。。。
var n,i,j,t:longint;
a,b,f:array[0..1001] of longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;
begin
readln(n);
readln(t);
for i:=1 to n do readln(a[i],b[i]);
for i:=1 to n do
for j:=t downto b[i] do
f[j]:=max(f[j],f[j-b[i]]+a[i]);
writeln(f[t]);
end.