cf478d 线性dp好题

/*
给定r个红块,g个绿块,按要求堆放
问当堆放成最大高度时,有多少种可能的堆放方式
排列要求:1.第i行放i块
2.每行同色 首先当然要确定能够放置几行
设红块有r个,绿块有g个,那么放置h行需要(h+1)h/2个
那么r+g>=(h+1)h/2 => 2(r+g)>=(h+1)h => 2(r+g)>h*h
那么有 h=sqrt(2r+2g),然后再找符合条件的h 然后确定状态:dp[i][j]表示前i行用了j个红块的排列方案
转移方程:外层循环枚举i表示第i层,内层循环枚举j表示红块使用数
dp[i][j]=dp[i-1][j]+dp[i-1][j-i],即该行不用红块和用红块的两种决策
决策合法性:当j<i时这层只能用绿块
同时第i层红块至少用max(i(i+1)/2-g,0)个
初始状态,dp=0,r>0,dp[1][1]=1,g>0,dp[1][0]=1
用滚动数组优化
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans,h,dp[],r,g;
#define mod 1000000007
int main(){
cin>>r>>g;
h=sqrt(*r+*g);
while(h*(h+)/>(r+g))h--;
if(r>)dp[]=;
if(g>)dp[]=;
for(int i=;i<=h;i++){
int l=max((ll),(i+)*i/-g);
for(int j=r;j>=l;j--){
if(j>=i)dp[j]=(dp[j]+dp[j-i])%mod;
else dp[j]=dp[j];//只能用绿块
}
}
int l=max((ll),(h+)*h/-g);
for(int i=r;i>=l;i--)
ans=(ans+dp[i])%mod;
cout<<ans<<endl;
}
上一篇:数学概念 z


下一篇:mvc过滤器学习(1)