这鸟真会玩啊
查看原帖
这鸟真会玩啊
404249
yyhde3301楼主2021/7/26 23:02

我就纳闷了,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);
}


2021/7/26 23:02
加载中...