|
|
题解：
这是一道模仿现实的题目。它给的是长跟宽，你要知道。。现实中长跟宽是可以互换的。当然，你也可以这样再优化一下，可能存在长跟宽相同，价值不同的，保留最大的就好了。
注意。。题目中的切开是一切到底。不是任意切！！这样列出的DP方程是不一样的
刚开始我的DP方程是
i,j表示长为i,宽为j的空间
f[i][j]=max(f[i][j],f[i][j-k]+f[i][k],f[i-k][j]+f[k][j]) + 一点点优化。。 f[i][j]初始状态就是所给的一系列长跟宽跟价值.
f[p[k].x][p[k].y]=p[k].c
。。不过这样水不过去。
后来改写成2维的背包。593MS过掉。
dp[i][j]=max(dp[i-p[k].x][j]+p[k].c+dp[p[k].x][j-p[k].y],dp[i][j]，dp[i-p[k].x][p[k].y]+dp[i][j-p[k].y]+p[k].c);
要推出这条式子，你拿出一块草稿画一下就好了。 先中间切下去，然后在右边那小块再横着来一下。就是了。。
/*
* @author ipqhjjybj
* @date 20130724
*
*/
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string>
using namespace std;
#define inf 0x3f3f3f3f
#define MAXN 1005
#define clr(x,k) memset((x),(k),sizeof(x))
#define clrn(x,k) memset((x),(k),(n+1)*sizeof(int))
#define cpy(x,k) memcpy((x),(k),sizeof(x))
#define Base 10000
typedef vector<int> vi;
typedef stack<int> si;
typedef vector<string> vs;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define rep(i,n) for(int i = 0;i < n;++i)
#define foreach(it,c) for(vi::iterator it = (c).begin();it != (c).end();++it)
#define min(a,b) ((a)<(b)?(a):(b))
struct node{
int x,y,c;
}p[MAXN];
int dp[MAXN][MAXN];
int X,Y,n;
int max(int a,int b){
return a>b?a:b;
}
int main(){
//freopen("3127.in","r",stdin);
int T;
scanf("%d",&T);
while(T--){
clr(dp,0);
scanf("%d %d %d",&n,&X,&Y);
for(int i=0,a,b,c;i<n;i++){
scanf("%d %d %d",&a,&b,&c);
p[i<<1].x=a,p[i<<1].y=b,p[i<<1].c=c;
p[i<<1|1].x=b,p[i<<1|1].y=a,p[i<<1|1].c=c;
}
n <<=1;
for(int i=0;i<=X;i++)
for(int j=0;j<=Y;j++){
for(int k=0;k<n;k++){
if(i>=p[k].x&&j>=p[k].y){
dp[i][j]=max(max(dp[i-p[k].x][j]+p[k].c+dp[p[k].x][j-p[k].y],dp[i][j]),
dp[i-p[k].x][p[k].y]+dp[i][j-p[k].y]+p[k].c);
//printf("dp[%d][%d]=%d
",i,j,dp[i][j]);
}
}
dp[i][j]=max(dp[i][j],dp[i-1][j]);
dp[i][j]=max(dp[i][j],dp[i][j-1]);
}
printf("%d
",dp[X][Y]);
}
return 0;
}