题解

303 条题解

  • 0
    @ 2013-11-04 17:27:43

    var
    i,j,n,ans:longint;
    a,b,c,d,e:array[1..1000] of longint;
    begin
    readln(n);
    for i:=1 to n do
    read(a[i]);
    for i:=1 to n do
    begin
    b[i]:=1;
    c[i]:=1;
    end;
    for i:=n-1 downto 1 do
    for j:=i+1 to n do
    if (a[j]<a[i]) and (b[j]+1>b[i]) then b[i]:=b[j]+1;

    for i:=2 to n do
    for j:=i-1 downto 1 do
    if (a[j]<a[i]) and (c[j]+1>c[i]) then c[i]:=c[j]+1;

    for i:=1 to n do
    begin
    d[i]:=b[i]+c[i];
    if d[i]>ans then ans:=d[i];
    end;
    writeln(n-ans+1);
    end.

    正着找一遍,倒着再找一遍。

    • @ 2013-11-04 17:29:31

      纪念AC80!!!!!!!

  • 0
    @ 2013-10-29 17:16:27

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 536 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 536 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 536 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 536 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 536 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 544 KiB, score = 10
    Accepted, time = 0 ms, mem = 544 KiB, score = 100
    代码
    #include<cstdio>
    #include<algorithm>
    int n,h[101],a[101],b[101],r=0;
    int main(){
    scanf("%d",&n);
    for (int i=1; i<=n; i++) a[i]=b[i]=1;
    for (int i=1; i<=n; i++) scanf("%d",&h[i]);
    for (int i=1; i< n; i++)
    for (int j=0; j< i; j++) {
    if (h[1+i]>h[1+j]) a[1+i]=std::max(a[1+i],a[1+j]+1);
    if (h[n-i]>h[n-j]) b[n-i]=std::max(b[n-i],b[n-j]+1);
    } for (int i=1; i<=n; i++)r=std::max(r , a[i]+b[i]-1);
    printf("%d",n-r);
    }

  • 0
    @ 2013-10-26 11:35:41

    又A了一道 233
    动归求解,算两遍最长不升子序列
    var
    a,b,c:array[0..300]of integer;
    n,m,max,i,j:integer;
    begin
    readln(n);
    for i:=1 to n do begin read(a[i]);b[i]:=1;c[i]:=1 end;
    readln;
    for i:=n-1 downto 1 do begin
    m:=1;
    for j:=i+1 to n do
    if (a[j]<a[i])and (b[j]+1>m) then m:=b[j]+1;
    b[i]:=m
    end;
    //这一遍倒着算
    for i:=2 to n do begin
    m:=1;
    for j:=i-1 downto 1 do
    if (a[j]<a[i])and(c[j]+1>m) then m:=c[j]+1;
    c[i]:=m
    end;
    max:=0;
    for i:=1 to n do if (b[i]+c[i])>max then max:=b[i]+c[i];
    writeln(n-max+1);
    end.

  • 0
    @ 2013-10-24 16:20:10

    LIS+LDS
     
     

    #include <iostream>
    #include <fstream>

    using namespace std;

    const int MAX_SIZE = 100;

    int a[MAX_SIZE + 1], f[MAX_SIZE + 1], g[MAX_SIZE + 1];

    int main()
    {
    int N;
    cin >> N;

    int i, j, middle;
    for (i = 1; i <= N; i++) {
    cin >> a[i];
    }

    //
    // 分别求解以i为中间点(1<=i<=N)时的1~i最长上升序列和i~N最长下降序列的长度和,并保存最小值
    //
    int ans, MaxAns = 0, maxLenA, maxLenB;
    for (middle = 1; middle <= N; middle++) {
    f[1] = 1;
    for (i = 2; i <= middle; i++) {
    f[i] = 1;
    for (j = i - 1; j >= 1; j--) {
    if (f[j] + 1 > f[i] && a[i] > a[j]) f[i] = f[j] + 1;
    }
    }
    g[middle] = 1;
    for (i = middle + 1; i <= N; i++) {
    g[i] = 1;
    for (j = i - 1; j >= middle; j--) {
    if (g[j] + 1 > g[i] && a[i] < a[j]) g[i] = g[j] + 1;
    }
    }
    maxLenA = maxLenB = 0;
    for (i = 1; i <= middle; i++) {
    if (f[i] > maxLenA)
    maxLenA = f[i];
    }
    for (i = middle; i <= N; i++) {
    if (g[i] > maxLenB)
    maxLenB = g[i];
    }
    ans = maxLenA + maxLenB - 1;
    if (ans > MaxAns) MaxAns = ans;
    }

    //
    // 最少出队人数 = 总人数 - 最大保留人数(最长上升+最长下降)
    //
    cout << (N - MaxAns);

    return 0;
    }

  • 0
    @ 2013-10-02 13:25:29

    //本人的虽然代码很渣,但容易明白。计算出符合规则的有多少人,然后总数减去符合规则的便是ans。
    var
    n,i,j,ans:longint;
    f,g,h:array[1..200]of longint;
    procedure init;
    begin
    readln(n);
    for i:=1 to n do
    begin
    read(h[i]);
    f[i]:=1;g[i]:=1;
    end;
    end;

    procedure dpone;
    begin
    for i:=1 to n-1 do
    for j:=i+1 to n do
    if (h[i]<h[j]) and (f[i]>=f[j]) then f[j]:=f[i]+1;
    end;

    procedure dptwo;
    begin
    for i:=n downto 2 do
    for j:=i-1 downto 1 do
    if (h[i]<h[j]) and (g[i]>=g[j]) then g[j]:=g[i]+1;

    end;

    procedure print;
    begin
    ans:=0;
    for i:=1 to n do
    if ans<f[i]+g[i] then ans:=f[i]+g[i];
    ans:=n-ans+1;
    writeln(ans);
    end;

    begin
    init;
    dpone;
    dptwo;
    print;
    end.

    • @ 2013-10-02 13:26:13

      ans:=n-ans+1//+1是因为中间的人被-了2次。

  • 0
    @ 2013-08-20 15:14:39

    uses math;
    var a,up,down:array[1..100] of longint;
    n,i,j,m,len:longint;
    begin
    m:=0;
    readln(n);
    for i:=1 to n do
    read(a[i]);
    for i:=1 to n do up[i]:=1;
    for i:=1 to n do down[i]:=1;
    for i:=2 to n do
    begin
    len:=0;
    for j:=i downto 1 do
    if (a[j]<a[i])and(up[j]>len) then len:=up[j];
    if len>0 then up[i]:=len+1;
    end;
    for i:=n-1 downto 1 do
    begin
    len:=0;
    for j:=i to n do
    if (a[j]<a[i])and(down[j]>len) then len:=down[j];
    if len>0 then down[i]:=len+1;
    end;
    for i:=1 to n do
    m:=max(m,up[i]+down[i]-1);
    writeln(n-m);
    end.

  • 0
    @ 2013-08-20 15:05:27

    'uses math;
    var a,up,down:array[1..100] of longint;
    n,i,j,m,len:longint;
    begin
    m:=0;
    readln(n);
    for i:=1 to n do
    read(a[i]);
    for i:=1 to n do up[i]:=1;
    for i:=1 to n do down[i]:=1;
    for i:=2 to n do
    begin
    len:=0;
    for j:=i downto 1 do
    if (a[j]<a[i])and(up[j]>len) then len:=up[j];
    if len>0 then up[i]:=len+1;
    end;
    for i:=n-1 downto 1 do
    begin
    len:=0;
    for j:=i to n do
    if (a[j]<a[i])and(down[j]>len) then len:=down[j];
    if len>0 then down[i]:=len+1;
    end;
    for i:=1 to n do
    m:=max(m,up[i]+down[i]-1);
    writeln(n-m);
    end.'

  • 0
    @ 2013-08-13 20:26:07

    ###Block code
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define maxn 100

    int a[maxn+1],b[maxn+1],f[maxn+1],g[maxn+1],n;

    using namespace std;

    int main()
    {
    int i,j,k,t,y,maxx;
    while(~scanf("%d",&n))
    {
    for(i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    b[n-i+1]=a[i];
    }
    f[0]=0;
    for(i=1;i<=n;i++)
    {
    maxx=0;
    for(j=0;j<i;j++)
    if(a[j]<a[i]&&maxx<f[j]+1)maxx=f[j]+1;
    f[i]=maxx;
    }
    g[0]=0;
    for(i=1;i<=n;i++)
    {
    maxx=0;
    for(j=0;j<i;j++)
    if(b[j]<b[i]&&maxx<g[j]+1)maxx=g[j]+1;
    g[j]=maxx;
    }
    maxx=0;
    for(i=1;i<=n;i++)
    if(maxx<f[i]+g[n-i+1]-1)maxx=f[i]+g[n-i+1]-1;
    printf("%d\n",n-maxx);

    }
    return 0;
    }

  • 0
    @ 2013-08-13 20:20:19

    ###code blocks
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define maxn 100

    int a[maxn+1],b[maxn+1],f[maxn+1],g[maxn+1],n;

    using namespace std;

    int main()
    {
    int i,j,k,t,y,maxx;
    while(~scanf("%d",&n))
    {
    for(i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    b[n-i+1]=a[i];
    }
    f[0]=0;
    for(i=1;i<=n;i++)
    {
    maxx=0;
    for(j=0;j<i;j++)
    if(a[j]<a[i]&&maxx<f[j]+1)maxx=f[j]+1;
    f[i]=maxx;
    }
    g[0]=0;
    for(i=1;i<=n;i++)
    {
    maxx=0;
    for(j=0;j<i;j++)
    if(b[j]<b[i]&&maxx<g[j]+1)maxx=g[j]+1;
    g[j]=maxx;
    }
    maxx=0;
    for(i=1;i<=n;i++)
    if(maxx<f[i]+g[n-i+1]-1)maxx=f[i]+g[n-i+1]-1;
    printf("%d\n",n-maxx);

    }
    return 0;
    }

  • 0
    @ 2013-08-12 17:06:28

    =.=
    话说这道题难度为3?!

  • 0
    @ 2013-08-12 16:44:23

    =.= 好久不写 竟然忘了初始化Orz
    Var n,i,m,ans:longint;
    a:array[1..1000] of longint;
    Function max(a,b:longint):longint;
    Begin
    If a>b then exit(a) else exit(b);
    End;
    Function dijian(x:longint):longint;
    Var f:array[1..1000] of longint;
    i,j:longint;
    Begin
    For i:=1 to n do f[i]:=1;
    For i:=n-1 downto 1 do
    For j:=i+1 to n do
    If a[j]<a[i] then f[i]:=max(f[i],f[j]+1);
    Exit(f[x]);
    End;
    Function dizeng(x:longint):longint;
    Var f:array[1..1000] of longint;
    i,j:longint;
    Begin
    For i:=1 to n do f[i]:=1;
    For i:=2 to n do
    For j:=1 to i do
    If a[j]<a[i] then f[i]:=max(f[i],f[j]+1);
    Exit(f[x]);
    End;
    Begin
    readln(n);
    For i:=1 to n do read(a[i]);
    For i:=1 to n do ans:=max(ans,dizeng(i)+dijian(i)-1);
    writeln(n-ans);
    readln;
    End.

  • 0
    @ 2013-05-04 20:31:26

    ###Block code
    #include <cstdio>
    #include <cstring>
    #include <map>
    #include <cmath>
    #include <queue>
    #include <string>
    #include <stack>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    #define abs(x) ((x)>0?(x):-(x))
    #define __max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    #define rep(i,repstt,repend) for(int i=repstt;i<repend;i++)
    #define erep(i,repstt,repend) for(int i=repstt;i<=repend;i++)
    #define inf 0x7f//2147483647
    #define iinf 0x7fffffff
    #define PI acos(-1.0)
    #define NOBUG puts("No_Bug_Hear");
    #define STOP system("pause");
    #define FOUT freopen("out.txt","w",stdout);
    #define FIN freopen("in.txt","r",stdin);
    #define OUTCLOSE fclose(stdout);
    #define INCLOSE fclose(stdin);
    #define INIT(a,b) memset(a,b,sizeof(a))
    typedef long long ll;
    using namespace std;
    int lf[111],rt[111],tmax,f[111],n;
    int main(){
    //FIN
    //FOUT
    while(cin>>n){
    rep(i,0,n){
    lf[i]=rt[i]=1;
    cin>>f[i];
    }
    rep(i,0,n){
    rep(j,0,i)
    if(f[i]>f[j])
    lf[i]=
    max(lf[i],lf[j]+1);
    }
    for(int i=n-1;i>-1;i--){
    for(int j=n-1;j>i;j--)
    if(f[i]>f[j])
    rt[i]=__max(rt[i],rt[j]+1);
    }
    tmax=-1;
    rep(i,0,n)
    tmax=__max(tmax,rt[i]+lf[i]-1);
    cout<<n-tmax<<endl;
    }
    //INCLOSE
    //OUTCLOSE
    return 0;
    }

  • 0
    @ 2013-05-04 20:30:34

    #include <cstdio>
    #include <cstring>
    #include <map>
    #include <cmath>
    #include <queue>
    #include <string>
    #include <stack>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    #define abs(x) ((x)>0?(x):-(x))
    #define __max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    #define rep(i,repstt,repend) for(int i=repstt;i<repend;i++)
    #define erep(i,repstt,repend) for(int i=repstt;i<=repend;i++)
    #define inf 0x7f//2147483647
    #define iinf 0x7fffffff
    #define PI acos(-1.0)
    #define NOBUG puts("No_Bug_Hear");
    #define STOP system("pause");
    #define FOUT freopen("out.txt","w",stdout);
    #define FIN freopen("in.txt","r",stdin);
    #define OUTCLOSE fclose(stdout);
    #define INCLOSE fclose(stdin);
    #define INIT(a,b) memset(a,b,sizeof(a))
    typedef long long ll;
    using namespace std;
    int lf[111],rt[111],tmax,f[111],n;
    int main(){
    //FIN
    //FOUT
    while(cin>>n){
    rep(i,0,n){
    lf[i]=rt[i]=1;
    cin>>f[i];
    }
    rep(i,0,n){
    rep(j,0,i)
    if(f[i]>f[j])
    lf[i]=
    max(lf[i],lf[j]+1);
    }
    for(int i=n-1;i>-1;i--){
    for(int j=n-1;j>i;j--)
    if(f[i]>f[j])
    rt[i]=__max(rt[i],rt[j]+1);
    }
    tmax=-1;
    rep(i,0,n)
    tmax=__max(tmax,rt[i]+lf[i]-1);
    cout<<n-tmax<<endl;
    }
    //INCLOSE
    //OUTCLOSE
    return 0;
    }

  • 0
    @ 2013-04-09 21:46:01

    program p1098;
    var i,j,m,k,lb,n,w:longint;
    a,b,c,d:array[0..200]of longint;
    begin
    readln(n);
    for i:=1 to n do read(a[i]);
    lb:=1;
    b[1]:=1;
    c[1]:=1;
    for i:=2 to n do
    begin
    j:=1;
    while(a[b[j]]>=a[i])and(j<=lb)do
    inc(j);
    if j>lb then
    begin
    c[i]:=1;
    inc(lb);
    b[lb]:=i;
    end
    else
    begin
    c[i]:=c[b[j]]+1;
    w:=1;
    while c[i]<c[b[w]] do inc(w);
    for k:=lb downto w do b[k+1]:=b[k];
    b[w]:=i;
    inc(lb);
    end;
    end;
    fillchar(b,sizeof(b),0);
    lb:=1;
    b[1]:=n;
    d[n]:=1;
    for i:=n-1 downto 1 do
    begin
    j:=1;
    while(a[b[j]]>=a[i])and(j<=lb)do inc(j);
    if j>lb then
    begin
    d[i]:=1;
    inc(lb);
    b[lb]:=i;
    end
    else
    begin
    d[i]:=d[b[j]]+1;
    w:=1;
    while d[i]<d[b[w]] do inc(w);
    for k:=lb downto w do b[k+1]:=b[k];
    b[w]:=i;
    inc(lb);
    end;
    end;
    m:=0;
    for i:=1 to n do
    if m<c[i]+d[i]-1 then m:=c[i]+d[i]-1;
    write(n-m);
    end.

  • 0
    @ 2013-03-31 12:30:32

    噗。。错了好多次,真的要想好再写啊,不然真的悲剧了
    #include <cstdio>
    #include <cstring>
    #include <algorithm>

    const int N = 110;

    void solve(int *num, int dp[], int n){
    for(int i = 1;i <= n;i++){

    int Max = -1,loc = i;

    for(int j = 1;j < i;j++)

    if(num[i] > num[j]&&dp[j] > Max){

    loc = j;

    Max = dp[j];

    }

    dp[i] = dp[loc] + 1;

    }

    }

    int main(){
    int n, i, num1[N], num2[N], inc[N], dec[N];
    while(~scanf("%d", &n)){
    memset(inc, 0, sizeof(inc));
    memset(dec, 0, sizeof(dec));
    for(i = 1;i <= n;i++){
    scanf("%d", &num1[i]);
    num2[i] = num1[i];
    }
    std::reverse(num2 + 1, num2 + n + 1);//翻转数组 即1 2 3变成3 2 1
    solve(num1, inc, n);
    solve(num2, dec, n);
    int res = 10000;
    for(i = 1;i <= n;i++)
    res = std::min(res, n - (inc[i] + dec[n - i + 1] - 1));
    printf("%d\n", res);
    }
    return 0;
    }

  • 0
    @ 2012-11-08 14:58:34

    (⊙v⊙)嗯。。(⊙v⊙)嗯。。。我就是将其看做两组最长上升子序列b,c,循环顶点,再将其比较~

    代码!

    program xxg;

    var

    n,i,j,k,mix:longint;

    a,b,c:array[1..200]of longint;

    begin

    read(n);

    for i:=1 to n do read(a[i]);

    for i:=1 to n do

    begin

    b[i]:=1;

    for j:=1 to i-1 do

    if (a[i]>a[j])and(b[j]+1>b[i]) then inc(b[i]);

    end;

    for i:=n downto 1 do

    begin

    c[i]:=1;

    for j:=n downto i+1 do

    if (a[i]>a[j])and(c[j]+1>c[i]) then inc(c[i]);

    end;

    for i:=1 to n do

    if (b[i]+c[i])>mix then mix:=b[i]+c[i];

    mix:=n-mix+1;

    writeln(mix);

    end.

    是左搜一边,右搜一边。。。。。。。。。。

  • 0
    @ 2012-10-06 14:59:56

    var

    t:array[1..10000]of longint;

    c,d,e,n:longint;

    begin

    read(n);

    for c:=1to n do begin

    read(t[c]);

    if t[c]>t[c-1] then d:=c;

    end;

    c:=0;

    for e:=1 to (d-1) do

    if t[e]>=t[e+1] then c:=c+1;

    for e:=d to n do

    if t[e]

  • 0
    @ 2012-09-24 19:40:06

    var n,i,j,max:longint;

    a,c,d:array[1..1000] of longint;

    begin

    readln(n);

    for i:=1 to n do read(a[i]);

    for i:=1 to n do begin c[i]:=1;d[i]:=1;end;

    for i:=1 to n do

    begin

    for j:=1 to i-1 do

    if (a[j]

信息

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