程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 478D Red-Green Towers dp

Codeforces 478D Red-Green Towers dp

編輯:C++入門知識

Codeforces 478D Red-Green Towers dp


題目鏈接:點擊打開鏈接

題意:

給定r個紅色正方體,g個綠色正方體。

要求搭建一個高度為n的塔。

對於高度為n的塔,第一層積木個數必須為n,第二層必須為n-1,依次類推,每層比下面那層少一個。

且同一層顏色必須相同。

問:

我們設最高能搭建的塔的高度為h,問有多少種方法能搭建出高度為h的塔。


思路:

從最頂層開始構造。

設dp[i][j]表示前i層花了j個紅色木塊的方法數

因為每層的個數固定,所以知道花費紅色的個數,則就能馬上算出花費綠色的個數。

而且對於最高的高度,是和顏色無關的,只和r+g有關,YY得證。

或者直接dp上去,當這一次的方案數是0時,則上一次就是最高的高度了。

前i層可以用滾動數組優化掉。


#include 
#include 
#include 
#include 
#include 
#include 
#include 
template 
inline bool rd(T &ret) {
    char c; int sgn;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
template 
inline void pt(T x) {
    if (x <0) {
        putchar('-');
        x = -x;
    }
    if(x>9) pt(x/10);
    putchar(x%10+'0');
}
using namespace std;
typedef long long ll;
#define N 200010
const ll mod = 1e9+7;

ll r, g;
ll dp[2][N]; // dp[cur][i][j]表示剩下i個紅色,j=0最後一層是紅色
bool vis[N];
vectorG[2];
ll ok(){
    int cur = 0;
    memset(dp[cur], 0, sizeof dp[cur]);
    dp[cur][0] = 1;
    ll sum = 0;
    for(ll i = 0; ; i ++){
        cur ^= 1;
        sum += i;
        if( sum > r+g) break;
        memset(dp[cur], 0, sizeof dp[cur]);
        for(int j = 0; j <= r && j <= sum; j++)
        {
            if(sum - j + (i+1) <= g)
                dp[cur][j] += dp[cur^1][j], dp[cur][j] %= mod;
            if(j+(i+1)<=r)
                dp[cur][j+i+1] += dp[cur^1][j], dp[cur][j+i+1] %= mod;
        }
    }
    ll ans = 0;
    for(int i = 0; i <= r; i++){
        ans += dp[cur][i];
        if(ans >= mod) ans %= mod;
    }
    return ans;
}
int main() {
    while(cin>>r>>g){
        cout<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved