我就纳闷了,WA第八个点
第八个点输出:0 142
我的输出:0 141
求大佬帮忙查错,萌新改裂开了
方便大佬们帮忙查错,部分代码打了一丁点注释(嘻嘻
#include<bits/stdc++.h>
#define R register
#define min3(a,b,c) min(a,min(b,c))
using std::cout;using std::endl;using std::setw;
typedef long long ll;
const int inf=0x3f3f3f3f;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int n,m;
int blk[10010],blktp[10010],blkbtm[10010],blkc;
//block block top block bottom block count
int tp[10010],btm[10010];
// tp[i]和 btm[i]对应各个位置的上下界
int icrs[10010],mxicrs=0,dcrs[10010];
// increase,max increase,decrease
int f[2][2010];
int main(){
scanf("%d%d%d",&n,&m,&blkc);
for(R int i=1;i<=n;++i){
scanf("%d%d",&icrs[i],&dcrs[i]);
mxicrs=max(mxicrs,icrs[i]);
}
for(R int i=1,x;i<=blkc;++i){
scanf("%d",&x);x+=1;
blk[x]=1;
scanf("%d%d",&blkbtm[x],&blktp[x]);
}
for(R int i=1;i<=n+1;++i){
if(blk[i])
tp[i]=blktp[i]-1,btm[i]=blkbtm[i]+1;
else
tp[i]=m,btm[i]=1;
}
for(R int i=1;i<=m+mxicrs;++i){
f[0][i]=0;
f[1][i]=inf;
}
for(R int i=1,blkps=0;i<=n;++i){
for(R int j=1;j<=m;++j)
f[1][j+icrs[i]]=min3(f[1][j+icrs[i]],f[1][j]+1,f[0][j]+1);
for(R int j=1;j<=m;++j)
f[1][j-dcrs[i]]=min(f[1][j-dcrs[i]],f[0][j]);
for(R int j=m+mxicrs;j>=m;--j)
f[1][m]=min(f[1][m],f[1][j]);
// printf("x=%d:",i);
// for(int j=1;j<=m;++j)
// if(j>tp[i]||btm[i]>j)
// cout<<setw(4)<<"*";
// else
// cout<<setw(4)<<(f[0][j]==inf?-1:f[0][j]);
// printf("\n");
bool f1=0;
for(R int j=btm[i+1];j<=tp[i+1];++j)
if(f[1][j]<inf)
{f1=1;break;}
if(!f1)
{printf("0\n%d\n",blkps);return 0;}
if(blk[i])
++blkps;
for(R int j=1;j<=m+mxicrs;++j){
if(j>tp[i+1]||btm[i+1]>j)
f[0][j]=inf;
else
f[0][j]=f[1][j];
f[1][j]=inf;
}
}
R int mn=inf;
for(int i=1;i<=m;++i)
mn=min(mn,f[0][i]);
printf("1\n%d\n",mn);
}