#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 条评论
-
frankchenfu LV 8 @ 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
