社区讨论

实在调不出来的蒟蒻求助

P1941[NOIP 2014 提高组] 飞扬的小鸟参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi5hugb4
此快照首次捕获于
2025/11/19 12:19
4 个月前
此快照最后确认于
2025/11/19 12:19
4 个月前
查看原帖
CPP
#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)

回复

0 条回复,欢迎继续交流。

正在加载回复...