HDU 1069
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1069
題意：把給定的長方體（不限）疊加在一起，疊加的條件是，上面一個長方體的長和寬都比下面長方體的長
和寬短；求這些長方體能疊加的最高的高度.（其中（3，2，1）可以擺放成（3，1，2）、（2，1，3）等）.
思路：其實就是求最長的單調遞減序列。在長和寬的遞減下，求最大能得出的最大高度了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{int l,w,h;
}box[111];int dp[111];bool cmp(node a,node b)//長寬比較函數
{if(a.l>b.l) return true;if(a.l==b.l&&a.w>b.w) return true;return false;
}int main()
{int d[3],n,i,j,c=1,k,sumh;while(scanf("%d",&n)!=EOF&&n){k=0;for(i=0;i<n;i++){scanf("%d%d%d",&d[0],&d[1],&d[2]); sort(d,d+3);//將數據轉換成多種形式的長方體box[k].l=d[2];box[k].w=d[1];box[k].h=d[0];k++;box[k].l=d[2];box[k].w=d[0];box[k].h=d[1];k++;box[k].l=d[1];box[k].w=d[0];box[k].h=d[2];k++; } sort(box,box+k,cmp);//長寬排序for(i=0;i<k;i++) dp[i]=box[i].h;//初始化for(i=k-2;i>=0;i--)//跟一維的類似for(j=i+1;j<k;j++){if(box[i].l>box[j].l && box[i].w>box[j].w && dp[i]<dp[j]+box[i].h)dp[i]=dp[j]+box[i].h;}sumh=dp[0];for(i=0;i<k;i++)if(sumh<dp[i]) sumh=dp[i];printf("Case %d: maximum height = %d\n",c++,sumh);}return 0;
}
?
POJ3616
鏈接：http://poj.org/problem?id=3616
題目大意：
在一個農場里，在長度為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.x==b.x)return a.y<b.y;return a.x<b.x;
}
int main(){int n,m,t;scanf("%d%d%d",&n,&m,&t);for(int i=0;i<m;i++){scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].sum);p[i].y+=t;}sort(p,p+m,cmp);//這一步很關鍵，時間是有順序的for(int i=m-1;i>=0;i--){dp[i]=p[i].sum;for(int j=i+1;j<m;j++){if(p[j].x>=p[i].y)dp[i]=max(dp[i],dp[j]+p[i].sum);//轉移方程}}int maxx=0;for(int i=0;i<m;i++)maxx=max(maxx,dp[i]);cout<<maxx<<endl;return 0;
}
poj1088
http://poj.org/problem?id=1088
當初做的時候死也想不出dp順序，是腦子太死了，非想著按順序推，其實按高低排了序就很好搞了。
兩種思路：都是從小到大排序。可以以四周為條件更新自己，或者用自己做條件對別人更新。
dp(i,j)表示從點(i,j)出發的最長滑行長度。?
排序以后從小到大更新就保證了比它小的一定是正確的最長長度。
第一種思路：周圍比它小的里面挑dp最大的，再加一就ok
第二種思路：把周圍比它高的點都比較，需要更新就更新。舉個例子：if ?H(i+1,j) > H(i,j) ?// H代表高度dp(i+1,j) = max(dp(i+1,j),dp(i,j)+1)?
