TCO12 R1C 500pt : PasswordXGrid

解法

問題文よく分からなかったのでサンプルを眺めていたら最大値を求めるDPっぽかったのでその通り書いたら通った。

acceptされたコード

#include <vector>
#include <string>
using namespace std;

const int MAX_W = 41;
int dp[MAX_W + 1][MAX_W + 1];

struct PasswordXGrid {

	int minSum(vector <string> horizontal, vector <string> vertical) {
		const int H = horizontal.size(), W = horizontal[0].length() + 1;
		for(int i=0; i<H; ++i){
			for(int j=0; j<W; ++j){
				if(i!=H-1){
					dp[i+1][j] = max(dp[i+1][j], dp[i][j] + (vertical[i][j]&15));
				}
				if(j!=W-1){
					dp[i][j+1] = max(dp[i][j+1], dp[i][j] + (horizontal[i][j]&15));
				}
			}
		}

		return dp[H-1][W-1];
	}

};