题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1069
DP~~~
感觉有点类似二维的LIS。
好久没做题了,发现自己变水了很多,今天中午到的家,大概住20天~1个月吧,现在HDOJ的AC量是320,希望返校前能达到500,当然,如果仅此任务还不算很难,可是还有其他很多要学的,所以尽力吧。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include <iostream> #include <algorithm> using namespace std; typedef struct Block{ int l; // 长 int w; // 宽 int h; // 高 int sum; // 当前最长长度 }Block; int n; Block nBlocks[100]; int cnt = 0; // 按升序排列 bool cmp(Block m, Block n) { return (m.l*m.w < n.l*n.w); } // 如果n放m上面 bool isOK(Block m, Block n) { return (m.l>n.l && m.w>n.w) || (m.l>n.w && m.w>n.l); } int main() { freopen("input.txt", "r", stdin); int a, b, c; int temp; while(scanf("%d", &n)) { //cout << "n = " << n << endl; if(n == 0) break; ++cnt; for(int i=0; i<3*n; ++i) { scanf("%d %d %d", &a, &b, &c); //cout << a << " " << b << " " << c << endl; nBlocks[i].l=a, nBlocks[i].w=b, nBlocks[i].h=c, ++i; nBlocks[i].l=b, nBlocks[i].w=c, nBlocks[i].h=a, ++i; nBlocks[i].l=c, nBlocks[i].w=a, nBlocks[i].h=b; } sort(nBlocks+0, nBlocks+3*n, cmp); //for(int i=0; i<3*n; ++i) // cout << nBlocks[i].l << " " << nBlocks[i].w << " " << nBlocks[i].h << " " << nBlocks[i].l*nBlocks[i].w << endl; nBlocks[0].sum = nBlocks[0].h; for(int i=1; i<3*n; ++i) { temp = 0; for(int j=0; j<i; ++j) { if(nBlocks[j].sum>temp && isOK(nBlocks[i], nBlocks[j])) temp = nBlocks[j].sum; } nBlocks[i].sum = temp + nBlocks[i].h; } temp = 0; for(int i=0; i<3*n; ++i) { if(nBlocks[i].sum > temp) temp = nBlocks[i].sum; } printf("Case %d: maximum height = %d\n", cnt, temp); } return 0; } |
学习,学习。。。加油。。在这里学习。。。22