实在调不出来的蒟蒻求助

#include<cstdio>
#include<cstring>
#include<queue>
#define iinf 0x7f
#define inf 0x7f7f7f7f 
#define MAXN 10000
int length,maxheight,tot; 
struct Pipe{
    int upside;
    int downside;
}p[MAXN+1];
int f[2][MAXN+1]; 
int click[2][MAXN+1];
inline int min(int a,int b){
    return a<b? a:b; 
}
inline void init(){
    int place;
    scanf("%d%d%d",&length,&maxheight,&tot);
    for(int i=0;i<length;i++){
        scanf("%d%d",&click[1][i],&click[0][i]);
    }
    for(int i=0;i<=length;i++){p[i].downside=0;p[i].upside=maxheight+1;}
    while(tot--){
        scanf("%d",&place);
        scanf("%d%d",&p[place].downside,&p[place].upside);
    }
}
inline void dp(){
    memset(f,iinf,sizeof(f));   
    int i,j,now=0,last=1,cnt=0;
    bool flag;
    for(int i=1;i<=maxheight;i++) f[0][i]=0; 
    for(i=1;i<=length;i++){
        std::swap(now,last);
        flag=true;
        memset(f[now],iinf,sizeof(f[now]));
        for(j=1;j<=maxheight;j++)if(j+click[0][i-1]<=maxheight)
            f[now][j]=min(f[now][j],f[last][j+click[0][i-1]]);
        for(j=1;j<=maxheight;j++) if(j-click[1][i-1]>0)
            f[now][j]=min(f[now][j],min(f[now][j-click[1][i-1]],f[last][j-click[1][i-1]])+1);
        for(j=maxheight-click[1][i-1];j<=maxheight;j++) 
            f[now][maxheight]=min(f[now][maxheight],min(f[now][j],f[last][j])+1);
        for(j=1;j<=p[i].downside;j++) f[now][j]=inf;
        for(j=p[i].upside;j<=maxheight;j++) f[now][j]=inf;
        for(j=p[i].downside+1;j<p[i].upside;j++) if(f[now][j]<inf){flag=false;break;}
        //for(int k=1;k<=maxheight;k++) printf("%d ",f[now][k]);printf("\n");
        if(flag) {printf("0\n%d\n",cnt);return ;}
        if(p[i].upside!=maxheight+1) cnt++;
    }
    int ans=inf;
    for(j=p[length].downside+1;j<p[length].upside;j++) ans=ans<f[now][j]?ans:f[now][j];
    printf("1\n%d\n",ans);
}
int main(){
    init();
    dp(); 
    return 0;
} 

过不了第二个样例 (sad)

2 条评论

  • @ 2017-01-28 12:15:53
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define reg register
    #define oo 1000000000
    using namespace std;
    int n,m,t,f[10001][1001];
    struct node1
    {
        int l,h,x,y;
        bool b;
    }a[10001];
    int s()
    {
        reg char ch=getchar();
        reg int x=ch-'0';
        for(;(ch=getchar())>='0'&&ch<='9';) 
            x=x*10+ch-'0';
        return x;
    }
    int w(reg int r)
    {
        if(r>9)
            w(r/10);
        putchar(r%10+'0');
        return 1;
    }
    int main()
    {
        n=s();m=s();t=s();
        for(reg int i=0;i<n;i++)
            a[i].x=s(),a[i].y=s();
        for(reg int i=1;i<=n;i++)
        {
            a[i].l=1;
            a[i].h=m;
            a[i].b=0;
        }
        for(int i=1;i<=t;i++)
        {
            int p=s(),l=s(),h=s();
            a[p].l=++l;
            a[p].h=--h;
            a[p].b=1;
        }
        int ans=0;
        bool suc=1;
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                f[i][j]=oo;
                if(j-a[i-1].x>=1)
                f[i][j]=min(f[i][j],min(f[i-1][j-a[i-1].x]+1,f[i][j-a[i-1].x]+1));
            }
            for(int j=m-a[i-1].x;j<=m;j++)
                f[i][m]=min(f[i][m],min(f[i-1][j]+1,f[i][j]+1));
            for(int j=a[i].l;j<=a[i].h;j++)
                if(j+a[i-1].y<=m)
                    f[i][j]=min(f[i][j],f[i-1][j+a[i-1].y]);
            for(int j=0;j<=a[i].l-1;j++)
                f[i][j]=oo;
            for(int j=a[i].h+1;j<=m;j++)
                f[i][j]=oo;
            bool over=1;
            for(int j=1;j<=m;j++)
                if(f[i][j]<oo)
                {
                    over=0;
                    break;
                }
            if(over==1)
            {
                puts("0");
                w(ans);putchar('\n');
                break;
            }
            else
                if(a[i].b==1)
                    ans++;
        }
        if(suc==1)
        {
            ans=oo;
            for(int i=1;i<=m;i++)
            ans=min(ans,f[n][i]);
            puts("1");w(ans);putchar('\n');
        }
        return 0;
    }
    
  • @ 2017-01-28 12:15:40

    +1

  • 1

信息

ID
1907
难度
7
分类
动态规划 | 背包 点击显示
标签
递交数
3491
已通过
655
通过率
19%
被复制
8
上传者