大连网络赛之前做的一次模拟赛上见到&＃xff0c;开始想用贪心做&＃xff0c;但没想到好的贪心策略&＃xff0c;之后放下。这几天又重新看了看这道题&＃xff0c;有看了看网上的题解&＃xff0c;终于把这题A了&＃xff01;。
思路&＃xff1a;
如图&＃xff1a;
布的总大小为(xx, yy)。剪下的面积为(x, y); 注意这句话&＃xff1a; a machine which can cut one cloth into exactly two smaller rectangular pieces horizontally or vertically
所以可行的剪法有四种&＃xff0c;即&＃xff1a;
由上图可得动态转移方程为&＃xff1a;
dp[i][j] &＃61; max(dp[i][j], dp[i-x][j] &＃43; dp[x][j-y] &＃43; c[k]);
dp[i][j] &＃61; max(dp[i][j], dp[i][j-y] &＃43; dp[i-x][y] &＃43; c[k]);
dp[i][j] &＃61; max(dp[i][j], dp[i-y][j] &＃43; dp[y][j-x] &＃43; c[k]);
dp[i][j] &＃61; max(dp[i][j], dp[i][j-x] &＃43; dp[i-y][x] &＃43; c[k]);
My Code:
#include <iostream>
#include <cstdio>
#include <cstring>
#pragma comment(linker,"/STACK:65536000");
using namespace std;
const int N &＃61; 1002;
int dp[N][N];
int w[11][2], c[11];
int main()
{
//freopen("data.in", "r", stdin);
int t;
cin >> t;
while(t--)
{
int n, a, b, x, y, i, j, k;
cin >> n >> a >> b;
memset(w, 0, sizeof(w));
memset(c, 0, sizeof(c));
for(i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)
cin >> w[i][0] >> w[i][1] >> c[i];
for(i &＃61; 0; i <&＃61; a; i&＃43;&＃43;)
for(j &＃61; 0; j <&＃61; b; j&＃43;&＃43;)
dp[i][j] &＃61; 0;
for(i &＃61; 0; i <&＃61; a; i&＃43;&＃43;)
{
for(j &＃61; 0; j <&＃61; b; j&＃43;&＃43;)
{
for(k &＃61; 1; k <&＃61; n; k&＃43;&＃43;)
{
x &＃61; w[k][0];
y &＃61; w[k][1];
if(i >&＃61; x && j >&＃61; y)
{
dp[i][j] &＃61; max(dp[i][j], dp[i-x][j] &＃43; dp[x][j-y] &＃43; c[k]);
dp[i][j] &＃61; max(dp[i][j], dp[i][j-y] &＃43; dp[i-x][y] &＃43; c[k]);
}
x &＃61; w[k][1];
y &＃61; w[k][0];
if(i >&＃61; x && j >&＃61; y)
{
dp[i][j] &＃61; max(dp[i][j], dp[i-x][j] &＃43; dp[x][j-y] &＃43; c[k]);
dp[i][j] &＃61; max(dp[i][j], dp[i][j-y] &＃43; dp[i-x][y] &＃43; c[k]);
}
}
}
}
printf("%d\n", dp[a][b]);
}
return 0;
}
京公网安备 11010802041100号