11310:DELIVERY DEBACLE

UVa 動的計画法

問題文
http://uva.onlinejudge.org/external/113/11310.html

o

oo
o

の二つで縦2,幅nのブロックを作るパターン数を求めよ。






















↓類題。
http://d.hatena.ne.jp/TobiasGSmollett/20130618/1371579981

ooooooooo
ooooooooo
のように長さnのパターン数をf[ n ],

ooooooooo
 oooooooo
のように長さnの長方形から一個無くした形のパターン数をg[ n ]とすると

f[n]を作るのにAの部分を使ったとすると、f[ n ]は
Aooooooo 
oooooooo g[ n ]

+

oooooooo
Aooooooo g[ n ]

+

AAoooooo
Aooooooo g[ n - 1 ]

+

Aooooooo
AAoooooo g[ n - 1 ]

-

Aooooooo
Aooooooo f[ n - 1 ]


で求まる。最初のg[ n ]2個で

Aooooooo
Aooooooo

を2回数えてしまっているのでf[ n-1 ]を引く。

g[ n ]は

 ooooooo
Aooooooo f[ n - 1 ]

+

 Aoooooo
AAoooooo f[ n - 2 ]

よって、
g[ i ] = f[ i - 1 ] + f[ i - 2 ]
f[ i ] = 2 * g[ i ] + 2 * g[ i - 1 ] - f[ i - 1 ]

問題文より、
f[ 1 ] = 1, f[ 2 ] = 5, g[ 2 ] = 2
とした。

#include<iostream>
 
using namespace std;
 
typedef long long ll;

ll f[41],g[41],t,n;
 
int main(void){

  f[1]=1,f[2]=5,g[2]=2;

  for(int i=3;i<41;i++){
    g[i]=f[i-1]+f[i-2];
    f[i]=2*(g[i]+g[i-1])-f[i-1];
  }
  
  cin >> t;
  while(t--){
    cin >> n;
    cout << f[n] << endl;
  }
  return 0;
}

n=1のとき
o
o
の1通り。

n=2のとき
AA AA oA Ao
Ao oA AA AA
の4通り。

n=3のとき
AAB ABB
ABB AAB
の2通り。

n=3までのパターンで全部のブロックが作れる。
だから、dp[ 0 ] = 1として
dp[ i + 1 ] += dp[ i ] * 1
dp[ i + 2 ] += dp[ i ] * 4
dp[ i + 3 ] += dp[ i ] * 2
とやっても解ける。

#include<iostream>
 
using namespace std;
 
typedef long long ll;
 
ll t,n,dp[45];
 
int main(void){
 
dp[0]=1;
for(int i=0;i<45;i++){
dp[i+1]+=dp[i];
dp[i+2]+=dp[i]*4;
dp[i+3]+=dp[i]*2;
}
 
cin >> t;
while(t--){
cin >> n;
cout << dp[n] << endl;
}
return 0;
}