[TIOJ] 1452. 巧拼放置問題 (插頭DP/輪廓線DP)
題目連結: http://tioj.infor.org/problems/1452 就我所知，本題有兩種寫法，一種做法應該是被稱為「插頭DP/輪廓線DP」，想法不難，就是紀錄$dp[i][j][S]$為前$i-1$排都填滿了，且第$i$排由左往右$j$個也填滿了，而S則是記錄哪邊有凸出來(因為填滿也可以用直的填)，然後我這裡是往後轉移，轉移的方式也還算容易，就看他下一格是不是已經被填了(在S裡看)，如果沒被填就表示可以一個往下指的直的，且如果下兩格也沒被填就也可以擺一個橫的。最後看$dp[n-1][m-1][0]$即可。不過這題因為空間有點卡，所以要滾動一下。 #include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 15;
lld dp[2][N][(1<<N)+5];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n, m;
while(cin>>n>>m, n!=0 or m!=0){
if((n*m)&1){
cout<<"0\n";
continue;
}
if(m>n) swap(n,m);
fill(dp[0][0], dp[0][m-1]+(1<<m), 0);
dp[0][1][0]=1;
dp[0][0][1]=1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(j==m-1) fill(dp[(i+1)&1][0], dp[(i+1)&1][m-1]+(1<<m), ...