初学dp请高人指点 谁能告诉我用一维数组如何dp

program pp;

var

　　max,l:longint;

　　a,b,n,t,t1,v1:integer;

　　value:array[0..10000] of boolean;

　　time:array[0..10000] of integer;

　begin

　　readln(t,n);

　　fillchar(value,sizeof(value),false);

　　value[0]:=true;

　　for a:=1 to 10000 do

　　 time[a]:=10000;

　　for a:=1 to n do

　　 begin

　　　　readln(t1,v1);

　　　　max:=max+v1;

　　　　for b:=max downto v1 do

　　　　 if value=true then

　　　　　　begin

　　　　　　 if time>time+t1 then time:=time+t1;

　　　　　　 if time

经典的0-1背包问题

b[j]=max(b[j-tm[i]]+v[i],b[j])

#include

#include

#include

using namespace std;

int main()

{

int i,j;

int b[1001],tm[1001],v[1001];

for(int t,m;cin>>t>>m;)

{

for(i=1;i>tm[i]>>v[i];

}

memset(b,0,sizeof(b));

for(i=1;i=0;j--)

if(j>=tm[i]&&b[j-tm[i]]+v[i]>b[j])

b[j]=b[j-tm[i]]+v[i];

cout

program gg;

var

max,l:longint;

a,b,n,t,t1,v1:integer;

value:array[0..10000] of boolean;

time:array[0..10000] of integer;

begin

readln(t,n);

fillchar(value,sizeof(value),false);

value[0]:=true;

for a:=1 to 10000 do

time[a]:=10000;

for a:=1 to n do

begin

readln(t1,v1);

max:=max+v1;

for b:=max downto v1 do

if value=true then

begin

if time>time+t1 then time:=time+t1;

if time

Program medicine;

var a,b:array[1..1000] of longint;

f:array[0..1000,0..1000] of longint;

m,t,i,j:longint;

Function max(x,y:integer):integer;

begin

if x>y then max:=x

else max:=y;

end;

begin

readln(t,m);

for i:=1 to m do readln(a[i],b[i]);

f[0,t]:=0;

for i:=1 to m do

for j:=t downto a[i] do

f:=max(f,f+b[i]);

writeln(f[m,t]);

end.

#include

using namespace std;

int a[1001],b[1001],dp[1001][101]={0};

int main()

{int i,n,t;

cin>>t>>n;

for(i=1;i>a[i]>>b[i];

for (int i=1;i

又是个典型的包包问题

#include

using namespace std;

int main()

{

int t,n;

cin>>t>>n;

int a[n+1],b[n+1],c[n+1][t+1];

for (int i=1;i>a[i]>>b[i];

for (int i=0;i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program p1104;

const

maxt=1000;

maxm=100;

var

t,m,i,j:integer;

value,time:array[1..maxm] of integer;

f:array[0..maxt+1] of longint;

begin

readln(t,m);

for i:=1 to m do

readln(time[i],value[i]);

fillchar(f,sizeof(f),0);

for i:=1 to m do

for j:=t downto time[i] do

if f[j-time[i]]+value[i]>f[j]

then f[j]:=f[j-time[i]]+value[i];

writeln(f[t]);

end.

program caiyao;

var max:integer;

　　i,m:1..1000;j,t:1..1000;

　　a,w:array[1..100] of 1..100;

　　f:array[0..10001] of integer;

begin

　　readln(t,m);

　　for i:=1 to m do readln(a[i],w[i]);

　　for j:=a[1] to t do f[j]:=w[1];

　　for i:=2 to m do

　　 for j:=t downto a[i] do

　　 if f[j-a[i]]+w[i]>f[j] then f[j]:=f[j-a[i]]+w[i];

　　max:=0;

　　for j:=1 to t do

　　if f[j]>max then max:=f[j];

　　writeln(max);

end.

没错...一维数组就做掉了..... = =

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

#include

using namespace std;

main ()

{

int t,n;

cin>>t>>n;

int a[n+1],b[n+1],c[n+1][t+1];

for (int i=1;i>a[i]>>b[i];

for (int i=0;i

我用的是顺推法，开一个二维数组。f:=max(f+b[i],f) 第一次20,后来改了一下范围就过了

program p1104;

var

t,m,i,j:integer;

a,b:array [1..100] of longint;

f:array [0..1000,0..1000] of longint;

function max(a,b:integer):integer;

begin

if a>=b then max:=a else max:=b;

end;

begin

readln(t,m);

for i:=1 to m do

readln(a[i],b[i]);

fillchar(f,sizeof(f),0);

for i:=1 to m do

for j:=1 to t do

if j>=a[i] then f:=max(f+b[i],f)

else f:=f;

write(f[m,t]);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案错误...程序输出比正确答案长

├ 测试数据 03：答案错误...程序输出比正确答案长

├ 测试数据 04：答案错误...程序输出比正确答案长

├ 测试数据 05：答案错误...程序输出比正确答案长

├ 测试数据 06：答案错误...程序输出比正确答案长

├ 测试数据 07：答案错误...程序输出比正确答案长

├ 测试数据 08：答案错误...程序输出比正确答案长

├ 测试数据 09：答案错误...程序输出比正确答案长

├ 测试数据 10：答案错误...程序输出比正确答案长

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：10 有效耗时：0ms

无语啦 各位大牛看看我的程序哪里错啦...

我在自己机器上测试都正确啦...

晓得啦 f[101]太小啦 换f[1001] 全过 ...

我可怜的AC啊 白白提交啦 6次 ....

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

#include "stdio.h"

int f[1001];

int main()

{

int w,v,i,j,t,m;

scanf("%d%d",&t,&m);

memset(f,0,sizeof(f));

for(i=1;i=w;j--)

{

if (f[j]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

#include "stdio.h"

int main()

{

int t,n,i,j,k,max,max1;

int f[101][1001]={0},time[101]={0},v[101]={0};

scanf("%d%d",&t,&n);

for(i=1;i

program yao;

var b,a:array[1..100] of integer;

q,i,j,m,t:integer;

begin

read(t,m);

for i:=1 to m do

read(a[i],b[i]);

for i:=1 to m do

for j:=i to m do

if b[i]

#include

main()

{

int t,n;

int info[101][2];

int a[1001]={0};

int i,z;

scanf("%d %d",&t,&n);

for(i=1;ia[z])

{a[z]=a[z-info[i][0]]+info[i][1];}}}

printf("%d\n",a[t]);

}