社区讨论

求助,不会写本题滚动数组优化一维空间后的 DP 写法

CF478DRed-Green Towers参与者 2已保存回复 5

讨论操作

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

当前回复
5 条
当前快照
1 份
快照标识符
@mhj1owam
此快照首次捕获于
2025/11/03 19:16
4 个月前
此快照最后确认于
2025/11/03 19:16
4 个月前
查看原帖
CPP
// Problem: D. Red-Green Towers
// Contest: Codeforces - Codeforces Round 273 (Div. 2)
// URL: https://codeforces.com/contest/478/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
typedef long long LL;
const int N=700,M=1e3+5,MOD=1e9+7;
int calc(int x){
	return x*(x+1)/2;
}
LL f[N][M]; // f[i][j] 表示前 i 层红砖用了 j 个
void solve(){
	int r,g;
	cin>>r>>g;
	int n=0;
	while(calc(n+1)<=(r+g)*2) n++;
	// cout<<n<<endl;
	memset(f,0,sizeof f);
	f[0][0]=1;
	rep(i,1,n){
		rep(j,0,r){
			f[i][j]+=f[i-1][j-i];
			if(calc(i)-j<=g) f[i][j]+=f[i-1][j];
			f[i][j]%=MOD;
		}
	}
	per(i,n,1){
		LL res=0;
		bool flag=false;
		rep(j,0,r){
			if(calc(i)-j>g) continue;
			flag=true;
			res+=f[i][j];
			res%=MOD;
		}
		if(flag) return cout<<res,void();
	}
}
int main(){
	int T=1;
	while(T--){
		solve();
		// cout<<endl;
	}
	return 0;
}

回复

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

正在加载回复...