HDU FatMouse's Speed 基本DP

題意：要求找到的體重遞增，速度遞減的老鼠，并且輸出最長的長度數，而且輸出各自的序列數。Special Judge?

思路：先按體重由小到大排序，再找最長速度遞減序列。

轉移方程：mou[i].w>mou[j].w&&mou[i].s<mou[j].s&&dp[j]+1>dp[i]

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define clc(a,b) sizeof(a,b,sizeof(a))
#define LL long long
#include<cmath>
using namespace std;
int dp[1010];//表示以i結尾的最長長度
int rightt[1010];//最終輸出序列
int pre[1010];//記錄i的前驅是什么
struct node {
    int w,s,index;
} mou[1010];

bool cmp(node a,node b) {
    if(a.w!=b.w) return a.w<b.w;
    else return a.s>b.s;
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int k=1;
    while(scanf("%d%d",&mou[k].w,&mou[k].s)!=EOF) {
        mou[k].index=k;
        k++;
    }
    sort(mou+1,mou+k,cmp);
    clc(dp,1);
    clc(rightt,0);
    clc(pre,0);
    int tot=0;
    int last;
    for(int i=1; i<k; i++) {
        for(int j=1; j<i; j++) {
            if(mou[i].w>mou[j].w&&mou[i].s<mou[j].s&&dp[j]+1>dp[i]) {
                dp[i]=dp[j]+1;
                pre[i]=j;
                if(tot<dp[i]) {
                    tot=dp[i];
                    last=i;
                }
            }
        }
    }
    int r=last;
    int i=0;
    while(r!=0) {
        rightt[i++]=r;
        r=pre[r];
    }
    printf("%d\n",i);
    for(int j=i-1; j>=0; j--) {
        printf("%d\n",mou[rightt[j]].index);
    }
    return 0;
}

?