UVa 10520 : Determine it
問題リンク:http://uva.onlinejudge.org/external/105/10520.html
問題概要:
短いので略
解法:
式に従って頑張ってノートでシュミレーションして見た結果左したのあたりから戻るように埋めていくとよさそう・・・
だがしかし今回nが20しかないので、
最大20*20で毎回埋めて行っても良い
一回20*20のループを回して更新できる場所を探す
すると少なくとも1つは必ず見つかる
なので最大でも20*20*20*20回で必ず終わる
あと、jが1の時どうなるのかが書いていない(自分が読み取れなかっただけかも)ので、
その場合は0を入れると良い
コード:
#include<iostream> #include<cmath> #include<algorithm> #include<vector> #include<climits> #include<cassert> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define inf INT_MAX #define MAX 30 using namespace std; typedef long long ll; ll a[MAX][MAX]; int n; void compute(int j,int i) { if(a[i][j] != inf)return; if(i < j) { ll cost = -inf; bool in = false; REP(k,i,j) { in = true; if(a[i][k] == inf || a[k+1][j] == inf)return; cost = max(cost,a[i][k] + a[k+1][j]); } if(!in)cost = 0; if(cost == -inf)return; a[i][j] = cost; return; } else { ll cost_a,cost_b; cost_a = cost_b = -inf; if(i == n)cost_a = 0; else { bool in = false; REP(k,i+1,n+1) { in = true; if(a[k][1] == inf || a[k][j] == inf)return; cost_a = max(cost_a,a[k][1]+a[k][j]); } if(!in)cost_a = 0; if(cost_a == -inf)return; } if(j == 0)cost_b = 0; else { bool in = false; REP(k,1,j) { in = true; if(a[i][k] == inf || a[n][k] == inf)return; cost_b = max(cost_b,a[i][k]+a[n][k]); } if(!in)cost_b = 0; if(cost_b == -inf)return; } a[i][j] = cost_a + cost_b; return; } } int main() { while(cin >> n) { rep(i,n+1)rep(j,n+1)a[i][j] = inf; cin >> a[n][1]; bool update = true; while(update) { update = false; for(int y=n;y>=0;y--) { for(int x=0;x<=n;x++) { if(a[y][x] == inf) { compute(x,y); } if(a[y][x] == inf)update = true; } } } cout << a[1][n] << endl; } return 0; }