社区讨论
实在调不出来的蒟蒻求助
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 条回复,欢迎继续交流。
正在加载回复...