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));…