問題文: Planning Rolling Blackouts | Aizu Online Judge
現在見ている区間の上下左右の端で状態数32^4くらいでメモ化再帰った。
漸化式とかよく分からないのでソースを見てください。
二次元累積和使うと早いヨ!
一番面倒くさいのは、その中でさらに予備電力?が最大になるようなものを取らなきゃいけないということ。とりあえずpair使って実装してみた。pair使うと最大のグループ数を優先しつつ、予備電力も最大なものを取ってくれるので。
#include <iostream> #include <cstring> using namespace std; #define mp(a,b) make_pair(a,b) #define num first #define energy second #define INF (9999) typedef pair<int,int> pii; int H , W , S; int mat[40][40]; pii dp[40][40][40][40]; //[x1,x2) & [y1,y2)であるような区間を与えると部分和を計算する。 int count(int x1,int y1,int x2,int y2){ return mat[y2-1][x2-1] - mat[y2-1][x1-1] - mat[y1-1][x2-1] + mat[y1-1][x1-1]; } // [x1,x2) & [y1,y2)であるような区間を見ている。(重要) pii dfs(int x1 , int y1 , int x2 , int y2){ if(~dp[x1][y1][x2][y2].num) return dp[x1][y1][x2][y2]; //現在の区間だけを停電させたとき、必要になる電源量がSを越えていたら駄目 if(mat[H][W] - count(x1,y1,x2,y2) > S) return mp(-INF,INF); //今見ている区間を分割しなかった場合を初期値にしている。 pii ans = mp( 1 , S - ( mat[H][W] - count(x1,y1,x2,y2) ) ); for(int i = x1+1 ; i < x2 ; i++){ pii A = dfs(x1,y1,i,y2); pii B = dfs(i,y1,x2,y2); pii get = mp( A.num + B.num , min(A.energy,B.energy) ); ans = max( ans , get); } for(int i = y1+1 ; i < y2 ; i++){ pii A = dfs(x1,y1,x2,i); pii B = dfs(x1,i,x2,y2); pii get = mp( A.num + B.num , min(A.energy,B.energy) ); ans = max( ans , get); } return dp[x1][y1][x2][y2] = ans ; } int main(){ int t; while(cin >> H >> W >> S , H || W || S ){ memset(mat,0,sizeof(mat)); for(int i = 0 ; i < 40 ; i++) for(int j = 0 ; j < 40 ; j++) for(int k = 0 ; k < 40 ; k++) for(int l = 0 ; l < 40 ; l++) dp[i][j][k][l] = mp(-1,-1); //入力 + 累積和化 for(int i = 1 ; i <= H ; i++) for(int j = 1 ; j <= W ; j++) cin >> t , mat[i][j] = t + mat[i][j-1]; for(int i = 1 ; i <= H ; i++) for(int j = 1 ; j <= W ; j++) mat[i][j] += mat[i-1][j]; pii result = dfs(1,1,W+1,H+1); cout << result.num << " " << result.energy << endl; } }