首页 > 代码库 > hdu 3127 WHUgirls
hdu 3127 WHUgirls
题目:
链接:点击打开链接
题意:
武汉大学有很多漂亮的妹纸,,,,,,,他们有一块待剪的布,他们想把它剪成很多小块做围巾,每个人喜欢不同的风格,他们把每一块的价值写在了纸上,现在有一个机器,可以把一块布剪成两块矩形的布,要求你用这台机器把原始的大布剪成纸上出现的小布,他们希望的到小块布的价值最大,当然不要求用完所有的布。。
思路:
首先它是一个背包问题:1>大布尺寸是总容量,每个小布都有相应的费用,2>要求剪的小布的个数是不限的,3>每块小布都有价值,要求大布被裁剪后的最大价值,(完全背包中的背包的最大价值)。
max((dp[i-a[k].x][j]+dp[a[k].x][j-a[k].y]),(dp[i][j-a[k].y]+dp[i-a[k].x][a[k].y]))+a[k].c//a[k].c是当前块的价值, max((dp[i-a[k].x][j]+dp[a[k].x][j-a[k].y]),(dp[i][j-a[k].y]+dp[i-a[k].x][a[k].y]))//剩余块的的最大价值
代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; struct node { int x; int y; int c; }a[11]; int dp[1005][1005]; int main() { int N,X,Y,t; scanf("%d",&t); while(t--) { memset(dp,0,sizeof(dp)); scanf("%d%d%d",&N,&X,&Y); for(int i=0; i<N; i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c); for(int i=1; i<=X; i++) { for(int j=1; j<=Y; j++) { for(int k=0; k<N; k++) { if(i>=a[k].x && j>=a[k].y)//分两种情况, dp[i][j] = max(dp[i][j],max((dp[i-a[k].x][j]+dp[a[k].x][j-a[k].y]),(dp[i][j-a[k].y]+dp[i-a[k].x][a[k].y]))+a[k].c); if(i>=a[k].y && j>=a[k].x) dp[i][j] = max(dp[i][j],max((dp[i-a[k].y][j]+dp[a[k].y][j-a[k].x]),(dp[i][j-a[k].x]+dp[i-a[k].y][a[k].x]))+a[k].c); } } } printf("%d\n",dp[X][Y]); } return 0; }
------------------------------------------------------------------------------------
看了大牛的代码和讲解点击打开链接
------------------------------------------------------------------------------------
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。