题解

3 条题解

  • 1
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1000000+10;
    const int inf=0x3f3f3f3f;
    typedef long long ll;
    typedef double ddf;
    int n,m;
    int l[N],g[N],f[2][N][2],pr,nt;
    int t[2],s[2][N];
    int ass;
    void fuck(){
        memset(f,0x3f,sizeof(f));
        t[1]=0;
        for(int j=1;j<=3;j++){
            for(int k=g[j];k<=g[j]+2;k++){
                if(k>=g[1])s[1][++t[1]]=k;
            }
        }
        for(int i=1;i<=t[1];i++)f[1][i][0]=s[1][i]-g[1];
        pr=0,nt=1;
        for(int i=2;i<=n;i++){
            pr^=1,nt^=1;t[nt]=0;
            int lf=max(1,i-2),rf=min(n,i+2);
            for(int j=lf;j<=rf;j++){
                for(int k=g[j];k<=g[j]+2;k++){
                    if(k>=g[i])s[nt][++t[nt]]=k;
                }
            }
            for(int j=1;j<=t[nt];j++){
                f[nt][j][1]=f[nt][j][0]=inf;
                for(int k=1;k<=t[pr];k++){
                    if(s[pr][k]>s[nt][j])f[nt][j][0]=min(f[nt][j][0],f[pr][k][1]);
                    else if(s[pr][k]<s[nt][j])f[nt][j][1]=min(f[nt][j][1],f[pr][k][0]);
                    else f[nt][j][0]=min(f[nt][j][0],f[pr][k][0]),f[nt][j][1]=min(f[nt][j][1],f[pr][k][1]);
                }
                f[nt][j][0]+=s[nt][j]-g[i];
                f[nt][j][1]+=s[nt][j]-g[i];
            }
        }
        int re=inf;
        for(int i=1;i<=t[nt];i++)re=min(re,f[nt][i][0]);
        ass+=re;
    }
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&g[i]);
        fuck();
    //  cout<<ass<<endl;
        for(int i=1;i<=n;i++)g[i]=N-l[i];
        fuck();
        printf("%d",ass);
        return 0;
    }
    
  • -1
    @ 2017-06-05 18:06:40

    类似木梳的一道Dp的题目

    #include<algorithm>
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<cstdlib>
    #include<vector>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    using namespace std;
    inline const int Get_Int() {
        int num=0,bj=1;
        char x=getchar();
        while(x<'0'||x>'9') {
            if(x=='-')bj=-1;
            x=getchar();
        }
        while(x>='0'&&x<='9') {
            num=num*10+x-'0';
            x=getchar();
        }
        return num*bj;
    }
    int n,f[2][1000005][2],g[2][1000005],Length[1000005],Left[1000005],Right[1000005],cnt[2],Value[2][1000005],MinRight=0x7fffffff/2,MaxLeft=0;
    int Dp() {
        memset(f[1],0x3f,sizeof(f[1]));
        memset(g,0,sizeof(g));
        cnt[1]=0;
        for(int i=1; i<=3; i++)
            for(int j=Length[i]; j<=Length[i]+2; j++)
                if(j>=Length[1])Value[1][++cnt[1]]=j; //确定可选择的值的范围 
        for(int i=1; i<=cnt[1]; i++)f[1][Value[1][i]][0]=Value[1][i]-Length[1]; //更新答案 
        for(int i=2; i<=n; i++) {
            cnt[i%2]=0; //不清空f否则会超时 
            int st=max(1,i-2),ed=min(n,i+2);
            for(int j=st; j<=ed; j++)
                for(int k=Length[j]; k<=Length[j]+2; k++)
                    if(k>=Length[i])Value[i%2][++cnt[i%2]]=k;  //确定可选择的值的范围 
            for(int t=1; t<=cnt[i%2]; t++) {
                int j=Value[i%2][t];
                g[i%2][j]=g[i%2][j]=i; //记录当前位置 
                f[i%2][j][0]=f[i%2][j][1]=0x7fffffff/2; //初始值无穷大 
                if(g[((i-1+2)%2)][j]==i-1||i==2) { //必须要上一次被更新过(有值)才能更新 因为没给f初值所以要这么做 
                    f[i%2][j][0]=min(f[i%2][j][0],f[(i-1+2)%2][j][0]+j-Length[i]);
                    f[i%2][j][1]=min(f[i%2][j][1],f[(i-1+2)%2][j][1]+j-Length[i]);
                }
                for(int s=1; s<=cnt[(i-1+2)%2]; s++) {
                    int k=Value[(i-1+2)%2][s];
                    if(g[((i-1+2)%2)][k]==i-1||i==2) { //必须要上一次被更新过(有值)才能更新
                        if(k<j)f[i%2][j][1]=min(f[i%2][j][1],f[(i-1+2)%2][k][0]+j-Length[i]);
                        if(k>j)f[i%2][j][0]=min(f[i%2][j][0],f[(i-1+2)%2][k][1]+j-Length[i]);
                    }
                }
            }
        }
        int Min=0x7fffffff/2;
        for(int j=1; j<=cnt[n%2]; j++)Min=min(Min,f[n%2][Value[n%2][j]][0]);
        return Min;
    }
    int main() {
        n=Get_Int();
        for(int i=1; i<=n; i++) {
            Left[i]=Get_Int();
            Right[i]=Get_Int();
            MaxLeft=max(MaxLeft,Left[i]);
            MinRight=min(MinRight,Right[i]);
        }
        for(int i=1; i<=n; i++)Length[i]=MaxLeft-Left[i];
        int ans=Dp();
        for(int i=1; i<=n; i++)Length[i]=Right[i]-MinRight;
        printf("%d\n",ans+Dp());
        return 0;
    }
    
  • -2
    @ 2016-01-10 18:20:59

    虽然我没有AC但我来抢个沙发

  • 1

信息

ID
1832
难度
5
分类
(无)
标签
递交数
25
已通过
12
通过率
48%
上传者