https://vjudge.net/contest/430905#problem/C
給出貓的體重和對應的速度，要求是得到一個體重上升的子序列的同時，速度必須是嚴格下降的序列，
請輸出最長的這樣的子序列，并且輸出這些貓的原本的序號，
我們需要一個結構體來記錄貓的體重，速度和序號，按照速度下降來排序，最后轉化成了求體重的最長上升子序列，
這答案多種，取任意一個即可，
#include<iostream>
#include<algorithm>
using namespace std;
struct mouse
{
int a,b,c;
} m[1005];
bool cmp(mouse x,mouse y)
{
if(x.b!=y.b) return x.b>y.b;
else return x.a<y.a;
}
int main()
{
int n=0;
int x,y;
while(cin >> x>>y)
{
n++;
m[n].a=x;
m[n].b=y;
m[n].c=n;
}
sort(m+1,m+1+n,cmp);
int d[1005]={0},maxx=0,rr[1005];
for(int i=2; i<=n; i++)//這是最長上升子序列的套路
{
for(int j=i-1; j>=1; j--)
{
if(m[i].a>m[j].a&&m[i].b<m[j].b)
//限制體重的同時，別忘了速度是嚴格下降的
{
d[i]=max(d[j]+1,d[i]);//狀態轉移方程，用d標記了當前體重的最大長度
maxx=max(d[i],maxx);//一直更新子序列的最大長度
}
}
}
cout << maxx+1 << endl;
int r=maxx,minn=100000;
x=0;
for(int i=n;i>=1,r>=0;i--)
//這一步必須反向遍歷，后面的大的值一定是由前面小值得到的，而前面小值的后面不一定有大值
//這里的大是指子序列長度
{
if(d[i]==r&&m[i].a<minn)
{
rr[r]=m[i].c;//標記序號
minn=m[i].a;//更新當前長度最大值的體重的最大值
r--;
}
}
for(int i=0;i<=maxx;i++)
{
cout << rr[i]<< endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/273595.html
標籤：其他