社区讨论
求助,不会写本题滚动数组优化一维空间后的 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 条回复,欢迎继续交流。
正在加载回复...