ICPC 国内予選2016D ダルマ落とし AOJ 1611
パッと見シミュレーションか貪欲法かなと思って考えていたが一向に解法が浮かばなかったので解説を見ました。DPという発想が出てこなかった。こういう問題がでたら確実に通したい。
解法:
というようにすればよい。
#include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long long ll; typedef pair<int, int> P; typedef tuple<int, int, int> T; const ll MOD=1e9+7; const ll INF=1e18; int dx[]={1, -1, 0, 0}; int dy[]={0, 0, 1, -1}; int dp1[310][310]; int dp2[310]; int main(){ int n,w[310]; while(true){ cin >> n; if(n == 0)break; for(int i = 0;i < 305;i++){ //初期化 dp2[i] = 0; for(int j = 0;j < 305;j++){ dp1[i][j] = 0; } } for(int i = 0;i < n;i++)cin >> w[i]; for(int len = 1;len < n;len+=2){ for(int i = 0;i+len < n;i++){ int j = i + len; if(abs(w[i]-w[j]) <= 1 && (len == 1 || dp1[i+1][j-1] != 0)){ dp1[i][j] = dp1[i+1][j-1] + 2; }else{ for(int k = 1;i+k < j-1;k++){ if(dp1[i][i+k] != 0 && dp1[i+k+1][j] != 0){ dp1[i][j] = len+1; } } } } } for(int i = 1;i < n;i++){ dp2[i] = dp1[0][i]; for(int j = 0;j < i;j++){ dp2[i] = max(dp2[i],dp2[j]+dp1[j+1][i]); } } cout << dp2[n-1] << endl; } }