社区讨论

数据水成啥样了

P2254[NOI2005] 瑰丽华尔兹参与者 4已保存回复 4

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@mmbw1xwz
此快照首次捕获于
2026/03/04 18:23
6 天前
此快照最后确认于
2026/03/07 12:10
3 天前
查看原帖
观察下面的代码,我把注释位置的q[t]写成了q[h]
CPP
#include<iostream>
#include<bitset>
#include<cstring>
using namespace std;
#define int long long
int dp[2][205][205];
int n,m,X,Y,k;
bitset<205> a[205];
int q[205],h,t;
signed main(){
	ios::sync_with_stdio(0);
	cout.tie(0);cin.tie(0);
	cin>>n>>m>>X>>Y>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='x')a[i][j]=1;
		}
	}memset(dp,-0x3f,sizeof dp);
	dp[0][X][Y]=0;
	while(k--){
		int l,r,p;
		cin>>l>>r>>p;
		r-=l-1;
		if(p==1){
			for(int j=1;j<=m;j++){
				h=0;
				t=-1;
				for(int i=n;i>=1;i--){
					if(a[i][j]){
						t=h-1;
						continue;
					}while(t>=h && q[h]-i>r){
						h++;
					}while(t>=h && dp[0][i][j]>=dp[0][q[h]][j]+q[h]-i){//这里 
						t--;
					}q[++t]=i;
					dp[1][i][j]=dp[0][q[h]][j]+q[h]-i;
				}
			}
		}else if(p==2){
			for(int j=1;j<=m;j++){
				h=0;
				t=-1;
				for(int i=1;i<=n;i++){
					if(a[i][j]){
						t=h-1;
						continue;
					}while(t>=h && i-q[h]>r){
						h++;
					}while(t>=h && dp[0][i][j]>=dp[0][q[h]][j]+i-q[h]){//这里 
						t--;
					}q[++t]=i;
					dp[1][i][j]=dp[0][q[h]][j]+i-q[h];
				}
			}
		}else if(p==3){
			for(int i=1;i<=n;i++){
				h=0;
				t=-1;
				for(int j=m;j>=1;j--){
					if(a[i][j]){
						t=h-1;
						continue;
					}while(t>=h && q[h]-j>r){
						h++;
					}while(t>=h && dp[0][i][j]>=dp[0][i][q[h]]+q[h]-j){//这里 
						t--;
					}q[++t]=j;
					dp[1][i][j]=dp[0][i][q[h]]+q[h]-j;
				}
			}
		}else{
			for(int i=1;i<=n;i++){
				h=0;
				t=-1;
				for(int j=1;j<=m;j++){
					if(a[i][j]){
						t=h-1;
						continue;
					}while(t>=h && j-q[h]>r){
						h++;
					}while(t>=h && dp[0][i][j]>=dp[0][i][q[h]]+j-q[h]){//还有这里 
						t--;
					}q[++t]=j;
					dp[1][i][j]=dp[0][i][q[h]]+j-q[h];
				}
			}
		}memcpy(dp[0],dp[1],sizeof dp[0]);
	}int maxi=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			maxi=max(maxi,dp[0][i][j]);
		}
	}cout<<maxi;
	return 0;
}
就这样能拿80分,水到没边了

回复

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

正在加载回复...