b131. NOIP2006 2.开心的金明 -- NOIP2006普及組 | From: [140.224.84.127] | 發表日期 : 2013-11-06 21:15

#include <stdio.h>

#include <iostream>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

using namespace std;

int n, m, v, c, happy[25][30000]={};

int main(){

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

for(int i=1; i<=m; i++){

scanf("%d %d", &v, &c);

for(int j=n; j>v; j--) happy[i][j]=max(happy[i-1][j], happy[i-1][j-v]+v*c);

}

printf("%d\n", happy[m][n]);

return 0;

} 

用一维的AC了 用二维的不知道哪里错了？？

帮忙看看 

b131. NOIP2006 2.开心的金明 -- NOIP2006普及組 | From: [140.224.84.127] | 發表日期 : 2013-11-06 21:45

12000 18

2758 5

3500 3

1200 2

430 4

530 3

239 3

2630 4

500 2

1120 3

1430 3

1420 5

400 1

1500 3

666 3

521 4

2430 3

1400 2

3410 4

 

#include <stdio.h>

#include <iostream>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

using namespace std;

int n, m, v, c, happy[30000]={};

int main(){

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

while(m--){

scanf("%d %d", &v, &c);

for(int i=n; i>=v; i--) happy[i]=max(happy[i], happy[i-v]+v*c);

}

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

return 0;

}

 

#include <cstdio>

#include <iostream> 

using namespace std;

int dp[30001]={}, v, w, N, m;

int main(){

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

    for(int i=0; i<m; i++){

    scanf("%d %d", &v, &w);

for(int j=N; j>=v; j--) dp[j]=max(dp[j], dp[j-v]+v*w);

}

printf("%d\n", dp[N]); 

    return 0;

} 

 

我实在不知道这两个近乎一样的程序跑出来为什么会有差别（跟数组大小没关系)