Hatena::Grouptopcoder

TopCoder Memo@kagamiz

08.13.2013 (Tue)SRM 588 div1

\/ 大敗北 \/

xx-...

1508 -> 1416 (-84).

悔い改めましょう.

250 GUMIAndSongsDiv1

tone[i] の整列された順をうれしい順序としてDP を行うか, tone[i]の上限・下限を定めてgreedy を行えば良い. O(n^3).

なぜか謎1 次元DP をしてしまった... が, 自信なかったし遅くても確実に自信が持てるアルゴリズムを考える必要がありますね.

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long lint;

class GUMIAndSongsDiv1 {
	public:
		int maxSongs(vector <int> duration, vector <int> tone, int T)
		{
			int res;
			int dp[51][51];
			vector<pair<int, int> > v;
			
			for (int i = 0; i < tone.size(); i++)
				v.push_back(make_pair(tone[i], duration[i]));
			
			sort(v.begin(), v.end());
			for (int i = 0; i < 51; i++)
				for (int j = 0; j < 51; j++)
					dp[i][j] = 1000000000;
			
			for (int i = 0; i <= tone.size(); i++)
				dp[0][i] = 0;
			
			res = 0;
			for (int i = 1; i <= tone.size(); i++){
				for (int j = 1; j <= i; j++){
					for (int k = 1; k <= i; k++){
						if (k != 1 && i == j) continue;
						dp[k][i] = min(dp[k][i], dp[k - 1][j] + v[i - 1].second + (k != 0) * (v[i - 1].first - v[j - 1].first));
						if (dp[k][i] <= T) res = max(res, k);
					}
				}
			}
			
			return (res);
		}
};

450 KeyDungeonDiv1

dp[訪れた先][持っている赤鍵] = もっている緑鍵の最大値, でdp をする. 白鍵は分配してやれば良い.

#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <deque>
#include <cassert>

using namespace std;

typedef long long lint;

int dp[4096][265];

class KeyDungeonDiv1 {
	public:
		int maxKeys(vector <int> doorR, vector <int> doorG, vector <int> roomR, vector <int> roomG, vector <int> roomW, vector <int> keys)
		{
			int res;
			int N = doorR.size();
			
			memset(dp, -1, sizeof(dp));
			
			for (int i = 0; i <= keys[2]; i++)
				dp[0][keys[0] + i] = keys[1] + keys[2] - i;
			
			res = 0;
			for (int i = 0; i < 1 << N; i++){
				for (int j = 0; j < N; j++){
					if (!(i >> j & 1)){
						for (int k = 0; k < 265; k++){
							if (k >= doorR[j] && dp[i][k] >= doorG[j]){
								for (int l = 0; l <= roomW[j]; l++){
									dp[i | (1 << j)][k - doorR[j] + roomR[j] + l] = max(dp[i | (1 << j)][k - doorR[j] + roomR[j] + l], dp[i][k] - doorG[j] + roomG[j] + roomW[j] - l);
								}
							}
						}
					}
				}
			}
			
			for (int i = 0; i < 1 << N; i++) for (int j = 0; j < 265; j++) if (~dp[i][j]) res = max(res, dp[i][j] + j);
			
			return (res);
		}
};

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/kagamiz/20130813