最長増加部分列 | 動的計画法 | 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…

Block | Aizu Online Judge 特に難しいことはないけど、入力ケースが多いので少しめんどくさい。 int mp[105][105]; bool visited[105][105]; int w, h; int xs, ys; int xg, yg; int n; int col; int dx[]={-1,1,0,0}; int dy[]={0,0,1,-1}; void solve(int…

島の数 | Aizu Online Judge 教科書的なDFSの問題なんだが、入力ケースの終わりがちょっと特殊だった。 Patisserie | Aizu Online Judgeを彷彿とさせる。。 bool visited[13][13]; string mp[13]; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; void solve(int…

整数の和 | Aizu Online Judge こちらも玉に引き続き、シンプルに全通り試してみる。 int n, s; int solve(int now, int left, int sum) { if (left == 0) { return sum == s; } if (now > 9) return 0; int res = 0; res+=solve(now+1, left-1, sum+now); r…

玉 | Aizu Online Judge シンプルな深さ優先探索。全通り試してOK。 int tama[11]; bool solve(int i, int n) { if (i == 10) { int al=-1, bl=-1; for (int j = 0; j < 10; j++) { if ((1<

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,>…