首页 > 代码库 > HDU 5087 (线性DP+次大LIS)
HDU 5087 (线性DP+次大LIS)
题目链接: 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。
#include "cstdio"#include "cstring"#include "iostream"using namespace std;int a[1005];struct status{ int fir,sec; status() {} status(int fir,int sec):fir(fir),sec(sec) {}}f[1005];int main(){ //freopen("in.txt","r",stdin); int T,n; scanf("%d",&T); while(T--) { int fir=0,sec=0; memset(f,0,sizeof(f)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { f[i]=status(1,0); for(int j=1;j<i;j++) { if(a[i]>a[j]) { if(f[j].fir+1>=f[i].fir) { f[i].sec=max(f[i].fir,f[j].sec+1); f[i].fir=f[j].fir+1; } else f[i].sec=max(f[i].sec,f[j].fir+1); } } if(f[i].fir>=fir) { sec=max(f[i].sec,fir); fir=f[i].fir; } } printf("%d\n",sec); }}
| 12046191 | 2014-11-02 00:56:35 | Accepted | 5087 | 125MS | 240K | 1099 B | C++ | Physcal |
HDU 5087 (线性DP+次大LIS)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。