J - FatMouse's Speed

代码:

// Created by CAD on 2019/10/29.
#include <bits/stdc++.h>
using namespace std;

struct state{
    int pre=-1;
    int cnt=1;
}dp[1005];
struct mouse{
    int speed,weight;
    int id;
    bool operator<(mouse &m)
    {
        if(weight!=m.weight)
            return weight<m.weight;
        else return speed>m.speed;
    }
}m[1005];
void print(int n)
{
    if(n==-1) return ;
    print(dp[n].pre);
    cout<<m[n].id<<endl;
}
int main()
{
//    FOPEN;
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n=0,ans=0;
    while(cin >> m[n].weight >> m[n].speed)
    {
        m[n].id=n+1;
        n++;
    }
    sort(m, m+n);
    for(int i=0; i<n; i++)
    {
        for(int k=0; k<i; ++k)
        {
            if(m[k].weight<m[i].weight && m[k].speed>m[i].speed&&dp[k].cnt+1>dp[i].cnt)
                    dp[i].cnt=dp[k].cnt+1, dp[i].pre=k;
        }
        if(dp[ans].cnt<dp[i].cnt)
            ans=i;
    }
    cout<<dp[ans].cnt<<endl;
    print(ans);
    return 0;
}
01-11 00:56