uva 10130-SuperSale(ゲージ、01リュック)

昨夜作ったテーマ、今夜貼ったコード、、、
昨夜はずっと問題が解決されていなかったので、今晩はやっと心を痛めていません.whyを知っています.
昨夜のコード、ずっとwa...

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
#define M 35
int p[N], w[N], dp[N][M];
int main ()
{
    int cas, n, m, ans, c;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; i++) scanf("%d %d",&p[i],&w[i]);
        for(int i = n; i >= 1; i--)
            for(int j = 30; j >= 0; j--)
            {
                dp[i][j] = (i==n?0:dp[i+1][j]);
                if(j>=w[i]) dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+p[i]);
            }
        ans = 0;
        scanf("%d",&m);
        for(int i = 0; i < m; i++)
        {
            scanf("%d",&c);
            ans+=dp[1][c];
        }
        printf("%d
",ans);
    }
    return 0;
}

幾つかの問題解きの報告書を見ても解けない.そこで私は黙って自分でやった.上のコードwaの原因は初期化問題で、dpは0に初期化すべきで、forループに初期化文があるとはいえ、次のmax関数のdp[i+1][j-w[i]]は境界を越えていますよ.第1組の配列n=30第2組のデータn=28であれば、dp[29][i]およびdp[30][i]は第1組の配列の値である.第2の配列による汚染.
ではなぜ次のコードを初期化しないのでしょうか.

        for(int i = 1; i <= n; i++)//     
            for(int j = 30; j >= 0; j--)
            {
                dp[i][j] = (i==1?0:dp[i-1][j]);
                if(j>=w[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+p[i]);
            }
        ans = 0;
        scanf("%d",&m);
        for(int i = 0; i < m; i++)
        {
            scanf("%d",&c);
            ans+=dp[n][c];
        }

簡単です.各配列はdp[0][i]に汚染を及ぼさない.だからdp[0][i]は永遠に0を保つ.初期化する必要はありません
一番簡単な方法はもちろん配列をスクロールします...
コードは次のとおりです.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
#define M 35
int p[N], w[N], dp[M];
int main ()
{
    int cas, n, m, ans, c;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; i++) scanf("%d %d",&p[i],&w[i]);
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= n; i++)
        for(int j = 30; j >= w[i]; j--)
        {
            if(dp[j]<dp[j-w[i]]+p[i]) dp[j] = dp[j-w[i]]+p[i];
        }
        ans = 0;
        scanf("%d",&m);
        for(int i = 0; i < m; i++)
        {
            scanf("%d",&c);
            ans+=dp[c];
        }
        printf("%d
",ans);
    }
    return 0;
}