题解

303 条题解

  • 4
    @ 2017-11-08 19:51:08

    毫无疑问这是一道DP(动态规划题)

    问题与最长上升(下降)序列有关
    解决了最长上升?下降问题之后
    面临的主要问题就是怎么选这个中间的人,我们看一看这个数据范围
    枚举完全可行啊!!!!!
    那么就枚举每个人作为中间的那个人(他也没说对称是吧)

    这个中间人需要保证左边是从左往右上升,右边是从左往右下降。
    所以找到每个人左边的最长上升子序列,右边的最长下降子序列(他本身一定是结尾)即可

    进行两遍操作,先进行一次最长上升子序列,再进行最长下降子序列,uppi【i】存的是选取第i个人当中间人左边的最长上升序列。down【i】存的是选取第i个人当中间人右边的最长下降序列右边最长下降序列(下降子序列其实就是倒着的上升序列)

    蒟蒻代码奉上

    #include <map>
    #include <set>
    #include <ctime>
    #include <queue>
    #include <stack>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define inf 0x3f3f3f3f
    using namespace std;
    inline int read()
    {
        int f=1,res=0;char ch = getchar();
        while(ch>'9'||ch<'0'){if(ch == '-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+ch-'0',ch=getchar();
        return f*res;
    }
    int n,uppi[105],down[105],a[105],ans;
    int main()
    {
        n=read();
        for(int i=1;i<=n;i++)   a[i] = read(),uppi[i] = down[i] = 1;
        for(int i=2;i<=n;i++) for(int j=1;j<i;j++) if(a[j] < a[i] && uppi[j] >= uppi[i]) uppi[i] = uppi[j] + 1;
        for(int i=n;i>=1;i--) for(int j=n;j>i;j--) if(a[j] < a[i] && down[j] >= down[i]) down[i] = down[j] + 1;
        for(int i=1;i<=n;i++)   ans = max( ans , uppi[i] + down[i] - 1 );           
        printf("%d",n-ans);
        return 0;
    }
    

    44msQAQ

  • 2
    @ 2017-04-25 12:53:25
    #include <iostream>
    #include <algorithm>
    #include <climits>
    using namespace std;
    
    const int maxn = 5000;
    int n, a[maxn], up[maxn], down[maxn];
    
    int main() {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        for (int i = 0; i < n; i++)
            up[i] = down[i] = 1;
        for (int i = 0; i < n; i++)
            for (int j = i - 1; j >= 0; j--)
                if (a[i] > a[j])
                    up[i] = max(up[i], up[j] + 1);
        for (int i = n - 1; i >= 0; i--)
            for (int j = i + 1; j < n; j++)
                if (a[i] > a[j])
                    down[i] = max(down[i], down[j] + 1);
        int result = 0;
        for (int i = 0; i < n; i++)
            result = max(result, up[i] + down[i] - 1);
        cout << n - result << endl;
        return 0;
    }
    
  • 2
    @ 2017-01-25 13:57:15
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int main()
    {
        int n,a[101],f[101],g[101],ans=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            f[i]=g[i]=1;
        }
        for (int i=1;i<=n;i++)
            for (int j=1;j<=i-1;j++)
                if (a[i]>a[j])
                    f[i]=max(f[i],f[j]+1);
        for (int i=n;i>=1;i--)
            for (int j=n;j>=i+1;j--)
                if (a[i]>a[j])
                    g[i]=max(g[i],g[j]+1);
        for (int i=1;i<=n;i++)
            ans=max(ans,f[i]+g[i]-1);
        printf("%d\n",n-ans);
    }
    
  • 1
    @ 2021-02-27 11:12:34

    经典dp
    那么怎么做呢(废话)
    先从左到右看每个人最多比几个人高,用f1记录下来
    从右到左也一样,(用f2记录)
    那么f1[i]+f2[i]-1就是第i人加上他自己可以形成的队形(注意要减一,因为从右往左时把自己多加了一遍)
    选出最大值
    用总人数-最多的队形人数(也就是那个最大值)就OK了

    
    #include<bits/stdc++.h>
    using namespace std;
    int n,a[105],m,f1[105],ans,f2[105];
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++)
        {
            m=0;
            for(int j=1;j<i;j++) if(a[i]>a[j]&&f1[j]>m) m=f1[j];
            f1[i]=m+1;
        }
        for(int i=n;i>0;i--)
        {
            m=0;
            for(int j=n;j>i;j--) if(a[i]>a[j]&&f2[j]>m) m=f2[j];
            f2[i]=m+1;
        }
        for(int i=1;i<=n;i++) if(f1[i]+f2[i]>ans) ans=f1[i]+f2[i];
        cout<<n-(ans-1);
    }
    
  • 1
    @ 2020-03-01 12:06:46

    在这里看效果更佳哦

    var
      a,b,c:array[1..100]of longint;
      max,i,j,n:longint;
    begin
      readln(n);
      for i:=1 to n do read(a[i]);
      for i:=1 to n do
        for j:=1 to i-1 do
          if (a[j]<a[i]) and (b[i]<b[j]+1) then b[i]:=b[j]+1;
      for i:=n downto 1 do
        for j:=i+1 to n do
          if (a[j]<a[i]) and (c[i]<c[j]+1) then c[i]:=c[j]+1;
      for i:=1 to n do
        if max<c[i]+b[i]+1 then max:=c[i]+b[i]+1;
      writeln(n-max);
    end.
    
  • 0
    @ 2019-03-09 17:14:29
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<iostream>
    using namespace std;
    int N,up[105],down[105],a[105],m;
    int main(){
        ios::sync_with_stdio(false);
        cin>>N;
        for(int i=1;i<=N;i++){
            cin>>a[i];
            up[i] = down[i] = 1;
        }
        for(int i=2;i<=N;i++){
            for(int j=1;j<i;j++){
                if(a[j]<a[i])
                    up[i] = max(up[i],up[j]+1);
            }
        }
        for(int i=N-1;i>=1;i--){
            for(int j=N;j>i;j--){
                if(a[j]<a[i])
                    down[i] = max(down[i],down[j]+1);
            }
        }
        for(int i=1;i<=N;i++) m = max(m,up[i]+down[i]-1);
        cout<< N-m;
    }
    
    
    
  • 0
    @ 2018-09-10 16:51:01

    #include <iostream>

    using namespace std;

    int main() {
    int f[2][105];
    int n;
    int height[105];
    for (int i = 0; i < 105; i++) {
    f[0][i] = 1;
    f[1][i] = 1;
    }
    cin >> n;
    for (int i = 0; i < n; i++) {
    cin >> height[i];
    }
    for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
    if (height[i] > height[j]) {
    if (f[0][i] < f[0][j] + 1) f[0][i] = f[0][j] + 1;
    }
    if (height[i] < height[j]) {
    if (f[1][i] < f[0][j] + 1) f[1][i] = f[0][j] + 1;
    if (f[1][i] < f[1][j] + 1) f[1][i] = f[1][j] + 1;
    }
    }
    }
    int max = 0;
    for (int i = 0; i < n; i++) if (max < f[1][i]) max = f[1][i];
    for (int i = 0; i < n; i++) if (max < f[0][i]) max = f[0][i];
    cout << n - max;
    return 0;
    }

  • 0
    @ 2018-08-09 09:43:32

    简单dp
    cpp
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,f1[110],f2[110],a[110],ans;
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
    f1[i]=1;
    for(int j=1;j<=i;j++)
    {
    if(a[i]>a[j]&&f1[j]+1>f1[i])f1[i]=f1[j]+1;
    }
    }
    for(int i=n;i>=1;i--)
    {
    f2[i]=1;
    for(int j=n;j>=i;j--)
    {
    if(a[i]>a[j]&&f2[j]+1>f2[i])f2[i]=f2[j]+1;
    }
    }
    for(int i=1;i<=n;i++)
    {
    if(f1[i]+f2[i]-1>ans)ans=f1[i]+f2[i]-1;
    }
    printf("%d\n",n-ans);
    return 0;
    }
    /*8 186 186 150 200 160 130 197 220*/

  • 0
    @ 2018-08-08 11:49:58
    /*dp*/
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int a[10001],h[10001],f[10001];
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            h[i]=f[i]=1;
            for(int j=1;j<i;j++)
            {
                if(a[j]<a[i]&&f[j]+1>f[i]) f[i]=f[j]+1;
            }
        }
        for(int i=n;i>=1;i--)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(a[j]<a[i]&&h[j]+1>h[i]) h[i]=h[j]+1;
            }
        }
        int max=-1;
        for(int i=1;i<=n;i++)
        {
            if(h[i]+f[i]-1>max) max=h[i]+f[i]-1;
        }
        printf("%d",n-max);
        return 0;
    }
    
  • 0
    @ 2018-04-15 12:34:48

    //合唱队形 vijos
    #include<iostream>
    using namespace std;

    #define maxn 101

    int dpup[maxn],dpdown[maxn],a[maxn];

    int main(){
    int i,j,ret,N,k;
    cin>>N;
    for(i=1;i<=N;i++){
    cin>>a[i];
    dpup[i]=dpdown[i]=1;
    }
    ret=1;
    for(i=1;i<=N;i++){
    for(j=1;j<i;j++){
    if(a[j]<a[i]){
    dpup[i]=max(dpup[i],dpup[j]+1);
    }
    }
    }

    for(i=N;i>=1;i--){
    for(j=i+1;j<=N;j++){
    if(a[j]<a[i]){
    dpdown[i]=max(dpdown[i],dpdown[j]+1);
    }
    }
    }

    for(i=1;i<=N;i++){
    ret=max(ret,dpdown[i]+dpup[i]-1);
    }

    cout<<N-ret<<endl;
    return 0;
    }

  • 0
    @ 2018-02-07 10:04:58

    Vijos的数据似乎并没有T1=T2=...=Tn的情况……
    O(n^3)算法:
    枚举中间的人,然后求两边的最长递增/递减子序列,注意必须保证两边的人都矮于中间的人

    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    const int maxN = 100 + 5;
    
    int dp[maxN];
    int T[maxN];
    int N;
    
    void input()
    {
        scanf("%d", &N);
        for (int i = 1; i <= N; i++)
            scanf("%d", T + i);
    }
    
    int try_solve(int mid)
    {
        for (int i = 1; i <= N; i++)
            dp[i] = 0;
    
        int maxL = 0, maxR = 0;
        for (int i = 1; i < mid; i++)
        {
            if (T[i] >= T[mid])
                continue;
            dp[i] = 1;
            for (int j = 1; j < i; j++)
                if (T[j] < T[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            maxL = max(maxL, dp[i]);
        }
    
        for (int i = mid + 1; i <= N; i++)
        {
            if (T[i] >= T[mid])
                continue;
            dp[i] = 1;
            for (int j = mid + 1; j < i; j++)
                if (T[j] > T[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            maxR = max(maxR, dp[i]);
        }
    
        return maxL + maxR + 1;
    }
    
    int solve()
    {
        int ans = 1;
        for (int i = 1; i <= N; i++)
            ans = max(ans, try_solve(i));
        return N - ans;
    }
    
    int main()
    {
        input();
        printf("%d\n", solve());
        return 0;
    }
    

    O(n^2)算法:
    dp[0][x]:以第x个人结尾的最长递增子序列
    dp[1][x]:以第x个人结尾,且已经开始递减的最长“合唱队形”
    状态转移过程:
    dp[0][x]也就是LIS
    dp[1][x]分两种情况(设k<x):
    (1)从dp[0][k]转移,也就是刚开始递减
    (2)从dp[1][k]转移

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int maxN = 105;
    const int inf = 0x3f3f3f3f;
    
    int a[maxN];
    int n;
    
    void input()
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d", a + i);
    }
    
    int dp[maxN][2];
    //0:increasing
    //1:decreasing
    
    int solve()
    {
        for(int i = 1; i <= n; i++)
        {
            dp[i][0] = 1;
            dp[i][1] = -inf;
        }
    
        for(int i = 2; i <= n; i++)
        {
            for(int j = 1; j < i; j++)
            {
                if(a[i] > a[j])
                    dp[i][0] = max(dp[i][0], dp[j][0] + 1);
            }
            for(int j = 2; j < i; j++)
            {
                if(a[i] < a[j])
                {
                    dp[i][1] = max(dp[i][1], dp[j][1] + 1);
                    //if(dp[j][0] >= 2)
                    dp[i][1] = max(dp[i][1], dp[j][0] + 1);
                }
            }
        }
    
        int opt = 0;
        for(int i = 1; i <= n; i++)
        {
            opt = max(opt, dp[i][1]);
            opt = max(opt, dp[i][0]);
        }
    
        return n - opt;
    }
    
    int main()
    {
        input();
        printf("%d", solve());
        return 0;
    }
    
    
  • 0
    @ 2017-11-01 20:55:51

    var
    n,i,j,k,ans1,ans2,max:longint;
    a,f:array[0..10000] of longint;
    begin
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do
    begin
    ans1:=0;ans2:=0;
    for j:=1 to i-1 do
    if a[j]<a[i] then begin
    f[j]:=1;
    for k:=1 to j-1 do
    if (a[k]<a[j])and(f[k]+1>f[j]) then f[j]:=f[k]+1;
    end;
    for j:=1 to i-1 do
    if f[j]>ans1 then ans1:=f[j];
    for j:=i+1 to n do
    if a[j]<a[i] then begin
    f[j]:=1;
    for k:=i+1 to j-1 do
    if (a[k]>a[j])and(a[k]<a[i])and(f[k]+1>f[j]) then f[j]:=f[k]+1;
    end;
    for j:=i+1 to n do
    if f[j]>ans2 then ans2:=f[j];
    if ans1+ans2+1>max then max:=ans1+ans2+1;
    end;
    writeln(n-max);
    end.

  • 0
    @ 2017-10-30 20:06:13

    #include <iostream>
    #include <cmath>
    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int ans=1;
    int main()
    {
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int i,j,n;
    cin>>n;
    int a[n+1],b[n+1],c[n+1];
    for (i=1;i<=n;i++) cin>>a[i];
    for (i=1;i<=n;i++)
    {
    b[i]=1;
    for (j=1;j<i;j++)
    {
    if (a[j]<a[i])
    {
    b[i]=max(b[i],b[j]+1);
    }
    }
    }
    for (i=n;i>=1;i--)
    {
    c[i]=1;
    for (j=n;j>i;j--)
    {
    if (a[j]<a[i])
    {
    c[i]=max(c[i],c[j]+1);
    }
    }
    }
    for (i=1;i<=n;i++)
    {
    ans=max(ans,c[i]+b[i]-1);
    }
    cout<<n-ans<<endl;
    system("pause");
    return 0;
    }

  • 0
    @ 2017-10-28 23:47:29

    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int up[500], down[500];
    int n; bool f1,f2;
    int a[500];
    int ans = 0x7f;
    int dp1[500], dp2[500];
    int pos,node;
    int upp(int r)
    {
    memset(dp1, 0x7f, sizeof(dp1));
    f1 = false;
    node = 0;
    for (int i=1; i<r; i++){
    pos = lower_bound(dp1, dp1+n+1, a[i]) - dp1;
    dp1[pos] = a[i];
    node = max(node, pos);
    }
    if (a[r] > dp1[node]) {
    f1 = true;
    dp1[++node] = a[r];
    }
    return node+1;
    // for (int i=1; i<=n; i++) cout<<dp1[i]<<" "; cout<<endl;
    // return upper_bound(dp1, dp1+n+2, 0x7f) - dp1;
    }

    int downn(int x){
    node = 0;
    f2 = false;
    memset(dp2, 0x7f, sizeof(dp2));
    for (int i=n; i>x; i--){
    pos = lower_bound(dp2, dp2+n+1, a[i]) - dp2;
    dp2[ pos] = a[i];
    node = max(node, pos) ;
    }
    if (a[x] > dp2[node]){
    dp2[++node] = a[x];
    f2 = true;
    }
    return node+1;
    // return upper_bound(dp2,dp2+n+2, 0x7f) - dp2;
    }

    int main(){
    cin>>n;
    for (int i=1; i<=n; i++)
    cin>>a[i];
    for (int i=2; i<n; i++){
    int u = upp(i); int v = downn(i); //i必选
    int now = n - u - v;
    if (f1 && f2) now++;
    // cout<<f1<<f2<<endl;
    // cout<<u<<" "<<v<<" "<<now<<endl;
    ans = min(ans, now);
    }
    ans = min (ans, n-upp(n));
    ans = min (ans, n-downn(1));
    cout<<ans<<endl;
    return 0;
    }

  • 0
    @ 2017-10-28 08:18:25

    最长上升+最长下降

    #include<bits/stdc++.h>
    using namespace std;
    int a[101];
    int f1[101];
    int f2[101];
    int main()
    {
        int n,ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            f1[i]=1;
            f2[i]=1;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<i;j++)
            {
                if(a[i]>a[j])
                {
                    f1[i]=max(f1[i],f1[j]+1);
                }
            }
        }
        for(int i=n;i>=1;i--)
        {
            for(int j=n;j>i;j--)
            {
                if(a[i]>a[j])
                {
                    f2[i]=max(f2[i],f2[j]+1);
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            ans=max(ans,f2[i]+f1[i]-1);
        }
        printf("%d",n-ans);
        return 0;
    }
    
  • 0
    @ 2017-10-26 19:18:22
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int a[200],b[200],c[200];
    int n,maxx;
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
        {
            b[i]=1;
            for(int j=1;j<=i-1;j++)
            {
                if(a[i]>a[j]&&b[j]+1>b[i])
                {
                    b[i]=b[j]+1;
                }
            }
        }
        for(int i=n;i>=1;i--)
        {
            c[i]=1;
            for(int j=i+1;j<=n;j++)
            {
                if(a[j]<a[i]&&c[j]+1>c[i])
                {
                    c[i]=c[j]+1;
                }
            }
        }
        maxx=0;
        for(int i=1;i<=n;i++)
        {
            if(b[i]+c[i]>maxx)
            {
                maxx=b[i]+c[i];
            }
        }
        cout<<n-maxx+1<<endl;
        return 0;
    }
    
  • 0
    @ 2017-10-21 08:14:49

    这不就是正向+反向取最长上升子序列。
    结束。

  • 0
    @ 2017-10-07 08:40:47
    #include<bits/stdc++.h>
    using namespace std;
    #define MAX 105
    int a[MAX],b[MAX],c[MAX];
    int main()
    {
        int n,i,j,maxx;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
        {
            b[i]=1;
            for(j=1;j<=i-1;j++)
            {
                if(a[i]>a[j]&&b[j]+1>b[i])
                    b[i]=b[j]+1;
            }
        }
        for(i=n;i>=1;i--)
        {
            c[i]=1;
            for(j=i+1;j<=n;j++)
            {
                if(a[j]<a[i]&&c[j]+1>c[i])
                c[i]=c[j]+1;
            }
        }
        maxx=-1;
        for(i=1;i<=n;i++)
        {
            if(b[i]+c[i]>maxx)
                maxx=b[i]+c[i];
        }
        printf("%d",n-maxx+1);
        return 0;
    }
    

    单调序列变体

  • 0
    @ 2017-09-01 15:48:29

    序列的正反向各做一次LIS,就能求出我们想要的队列形式的最优解了。
    还是很好想的~

    #include <iostream>
    using namespace std;
    int N;
    int A[105];
    int F[105], E[105];
    void DP () {
        
        for(int i=2; i<=N; i++)
            for(int j=1; j<i; j++)
                if (A[i]>A[j]) 
                    F[i]=max(F[i],F[j]+1);
        for(int i=N-1; i>=1; i--)
            for(int j=N; j>i; j--)
                if (A[i]>A[j]) 
                    E[i]=max(E[i],E[j]+1);              
        return;
        
    }
    int main () {
        
        cin >> N;
        for(int i=1; i<=N; i++) cin >> A[i];
        DP();
        int ans=0;
        for(int i=1; i<=N; i++) 
            ans=max(ans, F[i]+E[i]+1);
        cout << N-ans;    
        
    }
    
  • 0
    @ 2017-08-16 13:56:55
    '''
        最讨厌抄代码了
        放个python3
        应该能读懂(解释详尽)
        vijos 上测的AC记录
                        Accepted
            #      状态           耗时   内存占用
            #1   Accepted   39ms    3.324 MiB
            #2   Accepted   33ms    3.508 MiB
            #3   Accepted   31ms    3.367 MiB
            #4   Accepted   30ms    3.492 MiB
            #5   Accepted   31ms    3.438 MiB
            #6   Accepted   30ms    3.367 MiB
            #7   Accepted   37ms    3.379 MiB
            #8   Accepted   35ms    3.367 MiB
            #9   Accepted   32ms    3.367 MiB
            #10  Accepted   31ms    3.465 MiB
    '''
    import re;
    import sys;
    
    #这几个你们不用管
    def readmore():
        return map(int,sys.stdin.readline().split())
    def read():
        return int(input())
    
    def readarray():
        s = input()
        h = re.split(' ',s)
        l = [0,]
        for i in h:
            l.append(int(i))
        l.append(0)
        return l
    
    n = read()#读入n
    a = readarray()#读入a[1..n]
    
    f1 = [0 for i in range(n+3)]#初始化 f1 表示a每个点的上升子序列
    f2 = [0 for i in range(n+3)]#初始化 f2 表示a每个点的下降子序列
    
    for i in range(1,n+1):#for i=1->n
        for j in range(0,i):#for j=0->i-1
            if a[j]<a[i]:
                f1[i] = max(f1[j]+1,f1[i])#求原点到每个点之中最长上升子序列
    for i in range(n,0,-1):
        for j in range(i+1,n+2):
            if a[j]<a[i]:
                f2[i] = max(f2[j]+1,f2[i])#求每个点到结束点之中最长下降子序列
    MAX = 0
    for i in range(1,n+1):
        MAX = max (MAX,f1[i]+f2[i]-1)#算出最多可以多长(要减一)
    print(n-MAX)#输出(记得是剔除的不是留下的)
    

信息

ID
1098
难度
5
分类
动态规划 | LIS 点击显示
标签
递交数
12732
已通过
4825
通过率
38%
被复制
11
上传者