题目http://www.spoj.com/problems/CHOCOLA/
把一整块巧克力分成一个一个单元，掰断每一横行有个代价值，掰断每个纵行也有个代价值，要你求最后的总代价值最小
这个题目放在DP的题目列表里面，起初我是按DP的思想去解，先考虑只有一个单元的巧克力，再考虑2个单元，再是3个。。当把一个橫行都处理完再处理第二行，但是在处理第二行的时候就出问题了，到底此时是掰断橫行还是纵行，这里的操作会对之后造成影响，所以我这样，不是真正的最优子结构，因此这样DP就要出问题。后来发现原来直接贪心就可以了。
为了使总代价值最小，肯定要先掰断代价值最大的，这样使得那些代价值大的操作不会进行太多，因此结果肯定是最优的。所以先分别对 橫行代价值 与 纵行代价值 降序排序
在贪心过程中，需要注意一些细节，设置两个指针p q 分别指向此时橫行 和纵行 最大的代价值，每次比较这两个值，优先操作最大的，然后每次掰断了橫行的话，必定会引来一次纵行的全部拆散，反过来同样成立，。。。这个我也不知道怎么证明，不过确实是对的，。。其实我此刻靠在椅子上突然想明白为什么了，其实排序的过程，相当于把巧克力重新组合了一下，把价值大的横和纵 放在了最顶端 和 最右端，所以每次掰断相应的行列，就需要把那落单的一行 或者 一列 给全部拆解完！ （这个是关键！）
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define N 1005 using namespace std; bool cmp(int a,int b) { return a>b; } int x[N],y[N]; int m,n; int main() { int t; int i,j; scanf("%d",&t); while (t--) { scanf("%d%d",&m,&n); for (i=1;i<m;i++) { scanf("%d",&x[i]); } for (i=1;i<n;i++) { scanf("%d",&y[i]); } sort(x+1,x+m,cmp); sort(y+1,y+n,cmp); int p=1,q=1,ans=0; while (p<=m-1 || q<=n-1) { if (p<=m-1 && x[p]>=y[q]) { ans+=x[p]; for (j=q;j<=n-1;j++) //每次掰出了一段，就拆解它 下面同理。 ans+=y[j]; p++; } if (q<=n-1 && y[q]>x[p]) { ans+=y[q]; for (j=p;j<=m-1;j++) ans+=x[j]; q++; } if (p==m) { for (j=q;j<=n-1;j++) ans+=y[j]; q=n; } if (q==n) { for (j=p;j<=m-1;j++) ans+=x[j]; p=m; } } printf("%d ",ans); } return 0; }