CF478D Red-Green Towers

考虑a+b的最优情况，那么最大层数刚好为：sqrt(2*(a+b))。

有可能由于a与b相差较大，则不能到达这个理论最大层数，但是没有关系，我们在dp过程中，保证当前每一步的转移是合法的，则最后倒序枚举合法的最大层数即可。

对于dp状态的解释，写在了注释中。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+5,MOD=1e9+7;
int a,b,n;
int f[2][N],sum[N];
signed main(){
    scanf("%lld%lld",&a,&b);n=sqrt(2*(a+b));f[0][0]=1;//假设第1层为1个，第2层为2个...//f[i][j]:前i层做完，共用了j个第一种颜色的方案数 //理论复杂度nlogn，但MOD常数较大，而我们发现，n个1e9加起来不会爆longlong//所以我们可以先全部累加后，再进行一次取模来卡常 for (register int i=1; i<=n; ++i){
    int m=min(i*(i+1)/2,a);for (register int j=0; j<=m; ++j){
    if (i<=j) f[i&1][j]+=f[(i-1)&1][j-i];if (i*(i+1)/2-j<=b) f[i&1][j]+=f[(i-1)&1][j];f[i&1][j]%=MOD;}for (register int j=0; j<=m; ++j) sum[i]+=f[i&1][j];sum[i]%=MOD;for (register int j=0; j<=m; ++j) f[(i-1)&1][j]=0;}for (register int i=n; i>=1; --i) if (sum[i]) {
    printf("%lld\n",sum[i]);break;	}
return 0;
}