topcoder

kojingharangの日記

2012-04-15

TCO12 Round1C 500 PasswordXGrid

09:06 |

W x H グリッドの各辺にコストが与えられて、左上頂点から右下頂点に向かって後戻りしないで長さ W+H のパスで行くとき、どんなパスを通っても通ったとこのコストの和が同じになるように各辺のコストを大きくしたい。そうしたときのコストの和の最小値を求める問題。

一番コストが高いパスのコストの和が答えなので左上からDP
残り20分くらいしかなくて 250 がややこしかったので厳しいかなと思ったけど簡単でよかった

class PasswordXGrid {
	public:
	int minSum(vector <string> H, vector <string> V) {
		int N=H.size()-1;
		int M=H[0].size();
		VVI m(N+1, VI(M+1));
		cout<<M<<" "<<N<<endl;
		REP(y, N+1) {
			REP(x, M+1) {
				if(x-1>=0) m[y][x] = max(m[y][x], m[y][x-1]+H[y][x-1]-'0');
				if(y-1>=0) m[y][x] = max(m[y][x], m[y-1][x]+V[y-1][x]-'0');
			}
		}
		//cout<<m<<endl;
		return m[N][M];
	}
};