题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5087
题目大意：求次大LIS的长度。注意两个长度相同的LIS大小比较，下标和大的LIS较大。
解题思路：
结构体记录当前点的最大长fir，次长sec。
对于f[i].fir的转移，其实就是裸的LIS。
只不过当f[j].fir+1>=f[i].fir的时候也要转移，这时候尽管两个LIS长度相等，但是大小不一样。
对于f[i].sec的转移,首先它的初始值是0，在a[i]>a[j]条件下：
①首先当f[j].fir+1>=f[i].fir时：
我们肯定有最大长f[j].fir+1，剩下f[i].fir和f[j].sec+1，中出一个次长。
②当f[j].fir+1<f[i].fir时，此时最大长已经确定，但是却多出了个次长的可选值f[j].fir+1，注意得+1
HDU的数据略水，不+1也能水过去。
完成f[i]的转移之后，更新全局结果fir，sec。我一开SB地认为最后结果sec肯定在所有f[i].sec里面。
其实sec还可以是f[i].fir,它是全局的次长。
①如果f[i].fir>=fir(还是得相等，尽管长度一样)
此时次长有三个备选答案：fir,f[i].sec,sec，很明显fir>=sec,所以舍掉sec。
再更新一下最长fir。
②如果f[i].fir<fir，那么f[i].fir可能成为次长，HDU的数据略水，没有这步也能水过去。
#include "cstdio"
#include "cstring"
#include "iostream"
using namespace std;
int a[];
struct status
{
int fir,sec;
status() {}
status(int fir,int sec):fir(fir),sec(sec) {}
}f[];
int main()
{
//freopen("in.txt","r",stdin);
int T,n;
scanf("%d",&T);
while(T--)
{
int fir=,sec=;
memset(f,,sizeof(f));
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++)
{
f[i]=status(,);
for(int j=;j<i;j++)
{
if(a[i]>a[j])
{
if(f[j].fir+>=f[i].fir)
{
f[i].sec=max(f[i].fir,f[j].sec+);
f[i].fir=f[j].fir+;
}
else f[i].sec=max(f[i].sec,f[j].fir+);
}
}
if(f[i].fir>=fir)
{
sec=max(f[i].sec,fir);
fir=f[i].fir;
}
else sec=max(sec,f[i].fir);
}
printf("%d\n",sec);
}
}
| 12046191 | 2014-11-02 00:56:35 | Accepted | 5087 | 125MS | 240K | 1099 B | C++ | Physcal |