建网站石家庄,广州网页设计培训班,wordpress添加博主简介,加强政协机关网站建设HDU 1069
题目链接#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid1069
题意#xff1a;把给定的长方体#xff08;不限#xff09;叠加在一起#xff0c;叠加的条件是#xff0c;上面一个长方体的长和宽都比下面长方体的长
和宽短#xff1b;求这些长方体能…HDU 1069
题目链接http://acm.hdu.edu.cn/showproblem.php?pid1069
题意把给定的长方体不限叠加在一起叠加的条件是上面一个长方体的长和宽都比下面长方体的长
和宽短求这些长方体能叠加的最高的高度.其中321可以摆放成312、213等.
思路其实就是求最长的单调递减序列。在长和宽的递减下求最大能得出的最大高度了。
#includeiostream
#includecstdio
#includealgorithm
#includecstring
using namespace std;
struct node
{int l,w,h;
}box[111];int dp[111];bool cmp(node a,node b)//长宽比较函数
{if(a.lb.l) return true;if(a.lb.la.wb.w) return true;return false;
}int main()
{int d[3],n,i,j,c1,k,sumh;while(scanf(%d,n)!EOFn){k0;for(i0;in;i){scanf(%d%d%d,d[0],d[1],d[2]); sort(d,d3);//将数据转换成多种形式的长方体box[k].ld[2];box[k].wd[1];box[k].hd[0];k;box[k].ld[2];box[k].wd[0];box[k].hd[1];k;box[k].ld[1];box[k].wd[0];box[k].hd[2];k; } sort(box,boxk,cmp);//长宽排序for(i0;ik;i) dp[i]box[i].h;//初始化for(ik-2;i0;i--)//跟一维的类似for(ji1;jk;j){if(box[i].lbox[j].l box[i].wbox[j].w dp[i]dp[j]box[i].h)dp[i]dp[j]box[i].h;}sumhdp[0];for(i0;ik;i)if(sumhdp[i]) sumhdp[i];printf(Case %d: maximum height %d\n,c,sumh);}return 0;
}POJ3616
链接http://poj.org/problem?id3616
题目大意
在一个农场里在长度为N个时间可以挤奶但只能挤M次且每挤一次就要休息t分钟
其实不难脑子要灵活只要先对时间排序就好啦。
dp[i]表示i段最大值
#include cstdio
#include cstring
#include vector
#include iostream
#include algorithm
#include limits.h
#include cmath
#include queue
using namespace std;
int dp[10050];
struct sa{int x,y,sum;
}p[10050];
int cmp(const sa a,const sa b){if(a.xb.x)return a.yb.y;return a.xb.x;
}
int main(){int n,m,t;scanf(%d%d%d,n,m,t);for(int i0;im;i){scanf(%d%d%d,p[i].x,p[i].y,p[i].sum);p[i].yt;}sort(p,pm,cmp);//这一步很关键时间是有顺序的for(int im-1;i0;i--){dp[i]p[i].sum;for(int ji1;jm;j){if(p[j].xp[i].y)dp[i]max(dp[i],dp[j]p[i].sum);//转移方程}}int maxx0;for(int i0;im;i)maxxmax(maxx,dp[i]);coutmaxxendl;return 0;
}poj1088
http://poj.org/problem?id1088
当初做的时候死也想不出dp顺序是脑子太死了非想着按顺序推其实按高低排了序就很好搞了。
两种思路都是从小到大排序。可以以四周为条件更新自己或者用自己做条件对别人更新。
dp(i,j)表示从点(i,j)出发的最长滑行长度。
排序以后从小到大更新就保证了比它小的一定是正确的最长长度。
第一种思路周围比它小的里面挑dp最大的再加一就ok
第二种思路把周围比它高的点都比较需要更新就更新。举个例子if H(i1,j) H(i,j) // H代表高度dp(i1,j) max(dp(i1,j),dp(i,j)1)
