从最简单的开始：

POJ:

#include 
      
       #include 
       
        #include 
        
         using namespace std;int dp[111][111];int a[111][111];int main(){    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        for(int j=1;j<=i;j++)        {            scanf("%d",&a[i][j]);        }    }    memset(dp,0,sizeof(dp));    for(int i=1;i<=n;i++) dp[n][i] = a[n][i];    for(int i=n-1;i>=1;i--)    {        for(int j=1;j<=i;j++)        {            dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+a[i][j];        }    }    printf("%d\n",dp[1][1]);}
        
       
      

 

一维的转来转去，卡死了，结果换成二维的，轻松解决。清晰的体现了转移的特性。

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 5005;int dp[maxn][maxn];char s1[maxn];char s2[maxn];int main(){    while(scanf("%s %s",s1+1,s2+1)!=EOF)    {        int n = strlen(s1+1);        int m = strlen(s2+1);        int maxx = 0;        memset(dp,0,sizeof(dp));        for(int i=1;i<=n;i++)        {            for(int j=1;j<=m;j++)            {                if(s1[i]==s2[j])                {                    dp[i][j] = dp[i-1][j-1]+1;                }                else                {                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]); //两方程突出了转移                }            }        }        printf("%d\n",dp[n][m]);    }}/*127486 214786*/
        
       
      

 

思路清晰^_^

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn = 200;int dp[maxn];struct edge{    int l,r,h;};edge e[maxn];bool cmp(edge A,edge B){    if(A.l!=B.l) return A.l>B.l;    if(A.r!=B.r) return A.r>B.r;    if(A.h!=B.h) return A.h>B.h;}int main(){    int n,kase = 0;    while(scanf("%d",&n)!=EOF&&n)    {        int x,y,z;        for(int i=1;i<=3*n;i+=3)        {            scanf("%d %d %d",&x,&y,&z);            e[i].l = e[i+1].r = e[i+2].h = x;            e[i].r = e[i+1].h = e[i+2].l = y;            e[i].h = e[i+1].l = e[i+2].r = z;            if(e[i].l
        
       
      

 

n维的的最长上升子序列，不过需要打印路径，一个pre记录下。

在每一个box内部排序时，我差点写10个变量，不过最后学的姿势。

每次最愁做UVa题，网速慢死了。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int maxn = 40;int n,m;int pre[maxn];int dp[maxn];vector
           
             cnt;struct node{ int sq,edge[15];};node box[maxn];bool cmp(node A,node B){ for(int i=1;i<=m;i++) if(A.edge[i]!=B.edge[i]) return A.edge[i]>B.edge[i]; return A.edge[m]>B.edge[m];//以防全相等}int main(){ while(scanf("%d %d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) { box[i].sq = i; for(int j=1;j<=m;j++) { scanf("%d",&box[i].edge[j]); } sort(box[i].edge+1,box[i].edge+m+1); } sort(box+1,box+n+1,cmp); memset(dp,0,sizeof(dp)); memset(pre,0,sizeof(pre)); int maxn = 0; int ans = 0; int flag = 0; for(int i=1;i<=n;i++) { dp[i] = 1; for(int j=1;j
            
             =box[j].edge[k]) { flag = 1; break; } } if(!flag) { if(dp[i]
             
              maxn) { maxn = dp[i]; ans = box[i].sq; } } printf("%d\n",maxn); cnt.clear(); while(pre[ans]!=0) { cnt.push_back(ans); ans = pre[ans]; } cnt.push_back(ans); for(int i=0;i