777
by vocaloid @ 2019-04-02 21:20:00
@厂长可能长太chou了
by 明依 @ 2019-04-02 21:22:15
捧场
by 矢信 @ 2019-04-02 21:22:29
@[Vocaloid](/space/show?uid=52734) 7777
by 厂长 @ 2019-04-02 21:23:23
@[厂长](/space/show?uid=155831)
看红名大佬吊打我等
by 明依 @ 2019-04-02 21:23:57
@[Vocaloid](/space/show?uid=52734)
您的主页zhengyouyisi真有意思,orz
by 子归 @ 2019-04-02 21:24:10
@[小竹生](/space/show?uid=170518)
真有
by 子归 @ 2019-04-02 21:24:24
@[小竹生](/space/show?uid=170518) 我博客更有意思(
by vocaloid @ 2019-04-03 20:34:14
@[厂长](/space/show?uid=155831)
这是改后的代码
~~~~
#include<bits/stdc++.h>
using namespace std;
int n;
struct qwe{
int a,b,c;
}s[12000];
int tot;
int main() {
cin>>n;
for(int i=1; i<=n; i++) cin>>s[i].a;
for(int i=1; i<=n; i++) {
s[i].b=1;
for(int j=1; j<=i-1; j++) {
if(s[j].a<s[i].a&&s[j].b+1>s[i].b) {
s[i].b=s[j].b+1;
}
}
}
for(int i=n; i>=1; i--) {
s[i].c=1;
for(int j=n; j>=i; j--) {
if(s[i].a>s[j].a&&s[j].c+1>s[i].c) {
s[i].c=s[j].c+1;
}
}
}
tot=0;
for(int i=1; i<=n; i++) {
if(s[i].c+s[i].b>tot)
tot=s[i].c+s[i].b;
}
cout<<n-tot+1;
return 0;
}
~~~~
一个是第二次倒序找LIS,第二个是tot=0(这个赋不赋都无所谓)
必须倒序找的原因是这是个线性DP,按你的循环条件,你先找前面,但由于后面的序列数你没求出来,所以是求错的,只能倒序找。(我是蒟蒻QWQ,说不定在误导你)
by lanqinglian @ 2019-04-11 20:55:02
@[lanqinglian](/space/show?uid=145131)
抱歉,现在才看见
非常感谢
by 厂长 @ 2019-04-27 14:28:17