最長増加部分列 | 動的計画法 | Aizu Online Judge int a[1000*100+5] = {}; int main() { int n; cin >> n; fill(a, a + 1000*100+5, 1000*1000*1000*2); for (int i = 0; i < n; i++) { int t; cin >> t; *(lower_bound(a, a + 1000*100+5, t)) = t; } cou…

Knapsack Problem | Aizu Online Judge Combinatorial - 0-1 Knapsack Problem - アルゴリズムのメモ帳 とほぼ同じ問題。 続けて解いたので、ちょっとずるして上で解いたものを再利用した。 int main() { int N, W; cin >> N >> W; int v[105], w[105]; for …

ナップザック問題 | 動的計画法 | Aizu Online Judge シンプルなナップザック問題。 int main() { int N, W; cin >> N >> W; int v[105], w[105]; for (int i = 0; i < N; i++) cin >> v[i] >> w[i]; int dp[105][10005]; memset(dp, -1, sizeof(dp)); int r…

コイン問題 | 動的計画法 | Aizu Online Judge DPコースなるものを発見したので解いていこうと思う。 貪欲法でいける？と思ったが、コインの額面が半端なのでDPで解いていく。 int main() { int n, m; cin >> n >> m; int coins[25]; int dp[25][50005]; for…

Bingo | Aizu Online Judge 状態数をうまく削減しないといけない。 int N, M, S; int dp[50][3005]; int mod = 100000; int main() { while (1) { cin >> N >> M >> S; if (N == 0) break; memset(dp, 0, sizeof(dp)); N *= N; dp[0][0] = 1; for (int i = 1…

POJ 2441 : Arrange the Bulls 通ったんだけどこれでいいのかな。。 int N, M; int cows[30][30] = {}; int memo[(1 << 20) + 1] = {}; int solve(int i, int S) { if (memo[S] != -1) { return memo[S]; } if (i == N) return 1; int res = 0; for (int j =…

Lupin The 4th | Aizu Online Judge 巡回セールスマン問題。経路復元が必要。 経路復元は、それ用に配列をもう一つ用意しておいて、最短の移動順序を記録しておく。 double dp[100000][20]; int pos[100000][20]; int n; int kura[20], d[20], sen[20]; doub…

Patisserie | Aizu Online Judge 巡回セールスマン問題。 dp[すでに並べたケーキの集合][最後に置いたケーキ]としてメモ化再帰で解く。 グラフはG[ケーキv][ケーキu]として、ケーキvの次にケーキuを置く時、どれほど長さが増えるかで事前に作っておく。 同じ…

Russian Dolls DP。最長増加部分列。 int main() { while (1) { vector< pair<int, int> > vp; int dp[205]; int n; cin >> n; if (n == 0) break; for (int i = 0; i < n; i++) { int h, r; cin >> h >> r; vp.push_back(pair<int, int>(h, r)); } int m; cin >> m; for (int i </int,></int,>…

At Boss's Expense 一発で書けた。素数とナップザック問題。 bool dp[35][1000005]; bool pt[1000005]; int main() { memset(pt, 1, sizeof(pt)); pt[0] = 0; pt[1] = 0; for (int i = 2; i * i < 1000005; i++) { if (pt[i]) { for (int j = i*2; j < 10000…

泥棒 | Aizu Online Judge int main() { int cas = 1; while (1) { int N, W; int v[1005], w[1005], dp[1005][1005]; cin >> W; if (!W) break; cin >> N; for (int i = 0; i < N; i++) { char c; cin >> v[i] >> c >> w[i]; } memset(dp, -1, sizeof(dp));…