hdu 5410 dp

令dp[i][j][0]表示前i种物品花费最多j钱不买第i种物品可以获得的最大糖果数，dp[i][j][1]表示前i种物品花费最多j钱买第i种物品可以获得的最大糖果数，然后转移即可。第一维可以压缩掉。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 2001;
int dp[N][2];

int main ()
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        int m, n;
        scanf("%d%d", &m, &n);
        memset( dp, 0, sizeof(dp) );
        for ( int i = 1; i <= n; i++ )
        {
            int w, a, b;
            scanf("%d%d%d", &w, &a, &b);
            for ( int j = 0; j <= m; j++ )
            {
                dp[j][0] = max( dp[j][0], dp[j][1] );
            }
            for ( int j = w; j <= m; j++ )
            {
                dp[j][1] = max( dp[j - w][1] + a, dp[j - w][0] + a + b );
            }
        }
        printf("%d
", max( dp[m][0], dp[m][1] ));
    }
    return 0;
}