学步园

二维背包进阶版。。。。。

把布的大小当做背包的容量，长和宽就可以变成二维的。

但是。。。。。有两个不理解的地方，一是刚开始的时候我是把种类放到最外层去循环的，但是发现这样错掉了，要好好想一想循环的顺序的差别和意义。二是状态转移方程有些不一样。他是两个加起来的，虽然我看了题解感觉可以理解为什么这样，，，但是还要细想想。线上代码，跑得有点久。快四百了。

#include <stdio.h>
#include <string.h>
#include <iostream>
#define maxn 1010
using namespace std;
int n,xx,yy,sum;
int x[maxn],y[maxn],dp[maxn][maxn],cost[maxn];
void solve()
{
    memset(dp,0,sizeof(dp));
    int i,j,k;
    
      for(j=0;j<=xx;j++)
        for(k=0;k<=yy;k++)
            for(i=1;i<=n;i++)
        {
            if(j>=x[i]&&k>=y[i]) dp[j][k]=max(dp[j][k],max(dp[j-x[i]][y[i]]+dp[j][k-y[i]],dp[x[i]][k-y[i]]+dp[j-x[i]][k])+cost[i]);
            if(j>=y[i]&&k>=x[i]) dp[j][k]=max(dp[j][k],max(dp[j-y[i]][x[i]]+dp[j][k-x[i]],dp[y[i]][k-x[i]]+dp[j-y[i]][k])+cost[i]);
        }

    sum=dp[xx][yy];

    return;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        sum=0;
        scanf("%d%d%d",&n,&xx,&yy);
        for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&cost[i]);
        solve();
        printf("%d\n",sum);
    }
    return 0;
}