本文共 1496 字，大约阅读时间需要 4 分钟。

题目链接：

题目大意：

给出r个红砖，g个绿砖，问有多少种方法搭成最高的塔。

题目分析：

• 定义状态dp[i][j]表示构造i层的塔需要j块绿砖的方案数。
• 转移方程：
  dp[i][j]=dp[i−1][j−i]+dp[i−1][j]
  $$dp[i][j] = dp[i-1][j-i] + dp[i-1][j]$$
• 分别代表当前这一层放绿砖还是放红砖（当然要先判断当前状态转移是否合法）

  ---

AC代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define MAX 400007using namespace std;int dp[2][MAX];int r,g;const int mod = 1e9+7;int cal ( int h ){    return h*(h+1)/2;}int main ( ){    while ( ~scanf ( "%d%d" , &r , &g ) )    {        memset ( dp , 0 , sizeof ( dp ) );        dp[0][0] = 1;        int ans = 0;        for ( int i = 1 ;; i++ )        {            int x = i%2;            int y = (i+1)%2;            bool flag = true;            int low = cal ( i-1 );            int high = cal ( i );            for ( int j = 0; j <= high ; j++ )                dp[x][j] = 0;            for ( int j = 0; j <= high; j++ )            {                int jj = high - j;                if ( j > g || jj > r ) continue;                if ( j >= i )                {                    dp[x][j] += dp[y][j-i];                    dp[x][j] %= mod;                }                dp[x][j] += dp[y][j];                dp[x][j] %= mod;            }            bool mark = true;            int temp = 0;            for ( int j = 0 ; j <= high ; j++ )                if ( dp[x][j] )                 {                    mark = false;                    temp += dp[x][j];                    temp %= mod;                }            if ( mark ) break;            ans = temp;        }        printf ( "%d\n" , ans );    }}
      
     
    
   

转载地址：http://oqvjn.baihongyu.com/