FatMouse's Speed

这道题结合了结构体，还巧妙的利用结构体内部的对象记录了DP的前一状态的对象，感觉这种方法可以用在其他DP里，比如重建最长公共子序列。。

今天辛辛苦苦磨磨蹭蹭的做了两道DP，传上来记录一下

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#define Max(a,b) a>b?a:b
using namespace std;

struct Mouse
{
    int id;
    int weight;
    int speed;
    int link;
};

bool cmp(Mouse a, Mouse b)
{
    if(a.speed == b.speed) return a.weight > b.weight;
    else return a.speed > b.speed;
}

int main()
{
    Mouse mice[1005];
    Mouse temp;
    int m, w, s, n, t, max;
    int count[1005];
        memset(mice, 0, sizeof(mice));
        memset(count, 0, sizeof(count));
        int i;
        for(i=1; cin >> w >> s; i++)
        {
            temp.id = i;
            temp.link = -1;
            temp.weight = w;
            temp.speed = s;
            mice[i] = temp;
        }
        m = i-1;
        sort(mice+1, mice+m+1, cmp);
        for(int i=1; i<=m; i++)
            //cout << mice[i].id << " " << mice[i].weight << " " << mice[i].speed << endl;
        max = 1;
        temp = mice[1];
        count[1] = 1;
        for(int i=2; i<=m; i++)
        {
            for(int j=i-1; j>0; j--)
            {
                if(mice[j].weight < mice[i].weight)
                {
                    if(count[i] < count[j]+1)
                    {
                        count[i] = count[j]+1;
                        mice[i].link = j;
                    }
                }
            }
            if(count[i] > max)
            {
                max = count[i];
                temp = mice[i];
            }
        }
        int ans[1005] = {0};
        int num = 0;
        while(true)
        {
            ans[num] =  temp.id;
            num++;
            if(temp.link==-1) break;
            temp = mice[temp.link];
        }
        cout << num << endl;
        for(int i=num-1; i>=0; i--)
            cout << ans[i] << endl;
    return 0;
}