UVa-10401 : Injured Queen Problem
問題概要
キング+上下に動くようなクイーンに対して、Nクイーンが何通りあるか求める問題。いくつかのクイーンは配置が指定されている。
解法
ごくごく素直なDPだとO(N^3)。?のとき全部に配るのを止めて、全体に配って近くだけ差っ引くというやりかたをすればO(N^2)に落ちる。入力に空行含めたりするの本当に止めてほしい。
acceptされたコード
計算量O(N^2)。
#include <cstdio> #include <cstring> #include <cctype> #include <algorithm> #include <numeric> using namespace std; typedef long long int64; const int MAX_L = 15; char buf[MAX_L + 10]; int as[MAX_L]; int64 dp[MAX_L][MAX_L]; int64 dp2[MAX_L]; int to_num[0x100]; void pre(){ for(int i=0; i<9; i++){ to_num['1' + i] = i; } for(int i=0; i<6; i++){ to_num['A' + i] = i + 9; } } bool init(){ return gets(buf)!=NULL; } int64 solve(){ memset(dp, 0, sizeof(dp)); memset(dp2, 0, sizeof(dp2)); int L = strlen(buf); for(int i=0; i<L; i++){ if(buf[i] == '?'){ as[i] = -1; } else if(isdigit(buf[i]) || isalpha(buf[i])){ as[i] = to_num[buf[i]]; } else{ L = i; break; } } if(!L){ return -1; } if(as[0] == -1){ for(int i=0; i<L; i++){ dp[0][i] = 1; } } else{ dp[0][as[0]] = 1; } for(int i=1; i<L; i++){ for(int j=0; j<L; j++)if(dp[i-1][j] > 0){ if(as[i] == -1){ dp2[i] += dp[i-1][j]; if(j>0){ dp[i][j-1] -= dp[i-1][j]; } dp[i][j] -= dp[i-1][j]; if(j<L-1){ dp[i][j+1] -= dp[i-1][j]; } } else if(abs(j-as[i]) > 1){ dp[i][as[i]] += dp[i-1][j]; } } for(int j=0; j<L; j++){ dp[i][j] += dp2[i]; } } return accumulate(dp[L-1], dp[L-1] + L, 0LL); } int main(){ pre(); while(init()){ int64 ans = solve(); if(ans >= 0){ printf("%lld\n", ans); } } return 0; }