hdu1160 LIS变形

时间:2023-03-09 17:44:22
hdu1160 LIS变形

题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=1160

题意:两个子序列 一个是升序,一个是降序,求最长的子序列是多长,并输出路径。(答案不唯一)

思路都是一样的,不断的更新当前值,优化之前的值,只不过还要记录一下路径。

代码:(注释应该就可以看得懂了)//这注释,我给自己满分。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=1e6+; struct mice
{
int w,v,r,l; ///分别是体重,速度,位置,它下一个小鼠的位置
} m[maxn];
int dp[maxn]; ///dp代表到第i位老鼠的时候,排序能达到的最大长度 int cmp(mice a,mice b) ///体重降序排列,速度升序排列
{
if(a.w==b.w) return a.v<b.v;
else return a.w>b.w;
} int main()
{
int x,y,k=;
while(scanf("%d%d",&x,&y)==)
{
k++;
m[k].w=x;
m[k].v=y;
m[k].r=k;
m[k].l=;
}
sort(m+,m++k,cmp);
memset(dp,,sizeof(dp)); m[].w=INF; ///初始化m[0];
m[].v=;
m[].r=;
m[].l=; int ans=; for(int i=; i<=k; i++)
{
for(int j=; j<i; j++)
{
if(m[j].w>m[i].w && m[j].v<m[i].v)
{
if(dp[j]+>=dp[i]) ///dp[j]>=dp[i]时很好理解
{ ///那么dp[j]+1==dp[i]呢,就是使序列等长时,当前的体重值最小;
dp[i]=dp[j]+; ///长度+1
m[i].l=j; ///排好顺序后,第i只老鼠的下只老鼠是j;
if(dp[i]>dp[ans]) ans=i; ///找到当前长度的最大时的位置
}
} ///因为体重是降序排列,所以越往后i就可能是排在最前面的
} ///其实这就是一个插入的过程
}
printf("%d\n",dp[ans]);
while(m[ans].l!=) ///i越大,位置越靠前,所以从m[ans].r 开始输出。
{
printf("%d\n",m[ans].r); ///输出当前位置的原本位置
ans=m[ans].l; ///找到下一个位置
}
printf("%d\n",m[ans].r); ///输出排序最后一个位置的原本位置
return ;
}

代码2:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=1e6+; struct mice
{
int w,v,r,l; ///分别是体重,速度,位置,它下一个小鼠的位置
} m[maxn];
int dp[maxn]; ///dp代表到第i位老鼠的时候,排序能达到的最大长度 int cmp(mice a,mice b) ///体重降序排列,速度升序排列
{
if(a.w==b.w) return a.v<b.v;
else return a.w>b.w;
} int main()
{
int x,y,k=;
while(scanf("%d%d",&x,&y)==)
{
k++;
m[k].w=x;
m[k].v=y;
m[k].r=k;
m[k].l=;
}
sort(m+,m++k,cmp);
memset(dp,,sizeof(dp)); m[].w=INF; ///初始化m[0];
m[].v=;
m[].r=;
m[].l=; int ans=; for(int i=; i<=k; i++)
{
for(int j=; j<i; j++)
{
if(m[j].w>m[i].w && m[j].v<m[i].v)
{
if(dp[j]+>dp[i])
{
dp[i]=dp[j]+; ///长度+1
m[i].l=j; ///排好顺序后,第i只老鼠的下只老鼠是j;
if(dp[i]>dp[ans]) ans=i; ///找到当前长度的最大时的位置
}
} ///因为体重是降序排列,所以越往后i就可能是排在最前面的
} ///其实这就是一个插入的过程
}
printf("%d\n",dp[ans]);
while(m[ans].l!=) ///i越大,位置越靠前,所以从m[ans].r 开始输出。
{
printf("%d\n",m[ans].r); ///输出当前位置的原本位置
ans=m[ans].l; ///找到下一个位置
}
printf("%d\n",m[ans].r); ///输出排序最后一个位置的原本位置
return ;
}