dpまとめコン

試験期間中に全部理解したい。
A,Bはok
C,dp[I][j]:=I日目までで前日にjをしたときの幸福度総和maxとして解く

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
	int N;
	int a[100010][3];
	cin >> N;
	int dp[100010][3] = {};
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 3; ++j) {
			for (int k = 0; k < 3; ++k) {
				if (j != k) {
					dp[i+1][j] = max(dp[i][k] + a[i][j], dp[i+1][j]);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < 3; ++i) {
		ans = max(ans, dp[N][i]);
	}
	cout << ans << endl;
	return 0;
}
```

D
久しぶりのナップサック
dp[I][j]:=I番目までみて重量総和がjになるときの価値総和max

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
	int N, W;
	int v[110], w[110];
	ll dp[110][100010] = {};
	cin >> N >> W;
	for (int i = 0; i < N; ++i) {
		cin >> w[i] >> v[i];
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= W; ++j) {
			if (j >= w[i])dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
			else dp[i + 1][j] = dp[i][j];
		}
	}
	cout << dp[N][W] << endl;
	return 0;
}
```
E
ｄと問題は同じだが重さと価値の範囲が違う
数値のでかいほうを答えとして出力する。小さいほうを縛る条件にする。（そもそもでかいと配列で表しにくい）
今度は
dp[I][j]:=I番目まで見て価値総和がjになるときの重量総和minと設定する。

```#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
	int N;
	ll W;
	ll w[110], v[110];
	ll dp[110][100100];//dp[i][j]で価値総和がjになる時の重さ総和min
	cin >> N >> W;
	for (int i = 0; i < 110; ++i) {
		for (int j = 0; j < 100100; ++j) {
			dp[i][j] = INF;
		}
	}
	dp[0][0] = 0;
	for (int i = 0; i < N; ++i) {
		cin >> w[i] >> v[i];
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 100100; ++j) {
			if (j >= v[i]) {
				dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
			}
			else {
				dp[i + 1][j] = dp[i][j];
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= 100100; ++i) {
		if (dp[N][i] <= W)ans = i;
	}
	cout << ans << endl;
	return 0;
}
```
例題としてABC15のDがあるらしいのでこれもやってみた

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
	int W;
	int N, K;
	int A[51], B[51];
	int dp[51][51][10010];
	cin >> W >> N >> K;
	for (int i = 0; i < N; ++i) {
		cin >> A[i] >> B[i];
	}
	for (int i = 0; i < 51; ++i) {
		for (int j = 0; j < 51; ++j) {
			for (int k = 0; k < 10010; ++k) {
				dp[i][j][k] = 0;
			}
		}
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < K; ++j) {
			for (int k = 0; k <=W; ++k) {
				if (k >= A[i]) {
					dp[i + 1][j + 1][k] = max({ dp[i][j + 1][k], dp[i][j][k],dp[i][j][k - A[i]] + B[i] });
				}
				else {
					dp[i + 1][j + 1][k] = max(dp[i][j][k], dp[i][j + 1][k]);
				}
			}
		}
	}
	cout << dp[N][K][W] << endl;
	return 0;
}
```
F
LCS問題これも結構前にやったな覚えてねえ
dp[i+1][j+1]:=Sのi文字目までとTのj文字目まででのLCSの長さとする。
今まではdp[i]を使ってdp[i+1]を表したりしましたが今回はdp[i][j],dp[i+1][j],dp[i][j+1]を使ってdp[i+1][j+1]を表すことを考えると次のようになる
・S[i] == T[j]ならば、dp[i][j]に対して、共通のSのi文字目とTのj文字目を付け加えれば1文字伸びるので
dp[i+1][j+1] = dp[i][j]+1
・dp[i+1][j]に対して、Tのj文字目を考慮しても特にLCSの長さは変わらず、
dp[i+1][j+1] = dp[i+1][j]
・dp[i][j+1]に対して、Sのi文字目を考慮しても特にLCSの長さは変わらず、
dp[i+1][j+1]=dp[i][j+1]
まとめると
dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1] (S[i] == T[j]
dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])(S[i]!=T[j]

dp[0][0] = 0;
<求める値>
dp[|S|][|T|]

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
	string s, t;
	cin >> s >> t;
	int dp[3010][3010];
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < s.size(); ++i) {
		for (int j = 0; j < t.size(); ++j) {
			if (s[i] == t[j]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;
			}
			else {
				dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
			}
		}
	}
    //復元
	string res = "";
	int i = s.size(), j = t.size();
	while (i > 0 && j > 0) {
		//(i-1,j)->(i,j)と更新されていた場合
		if (dp[i][j] == dp[i - 1][j]) {
			--i;//DPの遷移を遡る
		}
		else if (dp[i][j] == dp[i][j - 1]) {
			--j;
		}
		//(i-1,j-1)->(i,j)と更新されていた場合
		else {
			res = s[i - 1] + res;//このときs[i-1]==t[j-1]なので、res+t[j-1]でもok
			--i, --j;
		}
	}
	cout << res << endl;
	return 0;
}
```
復元は初めてだった
例題abc130 E

```
int dp[2010][2010];//Sの最初i文字とTの最初j文字からできる共通部分列のうちSの
//最初のi文字目のラストとTの最初のj文字目のラストが等しくてかつこれを採用しているものの個数
//とするとdp遷移はs[i-1]==t[j-1]の部分について
//dp[i][j]=sum{0<=x<i,0<=y<j}dp[x][y]という風になる
//つまりdp[i未満][j未満]の総和ということ
//二次元累積和を用いて綺麗に更新する
//sdp[i+1][j+1]=sum{0<=x<=i,0<=y<=j}dp[x][y]とする
//とすると先ほどのdpの式はdp[i][j]=sdp[i][j]と簡潔に書ける。累積和の更新は
//sdp[i+1][j+1]=sdp[i+1][j]+sd[i][j+1]-sdp[i][j]+dp[i][j]でok
//最後の答えはsdp[N+1][M+1]になる
int main() {
	int n, m; cin >> n >> m;
	int s[2010], t[2010];
	for (int i = 0; i < n; ++i)cin >> s[i];
	for (int i = 0; i < m; ++i)cin >> t[i];
	
	return 0;
}
```

G　グラフ　再帰dp

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int N, M;
vector<vector<int>>G;
int dp[100100];
int rec(int v) {
	if (dp[v] != -1)return dp[v];//既に更新済み
	int res = 0;
	for (int i = 0; i < G[v].size();++i) {
		res = max(res, rec(G[v][i]) + 1);
	}
	return dp[v] = res;
}
int main() {
	cin >> N >> M;
	G.assign(N, vector<int>());//N個のvector<int>()を代入
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		G[a].push_back(b);
	}
	for (int v = 0; v < N; ++v) {
		dp[v] = -1;
	}
	int res = 0;
	for (int v = 0; v < N; ++v) {
		res = max(res, rec(v));
	}
	cout << res << endl;
	return 0;
}
```

H
迷路dp

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int H, W;;
vector<vector<char>>G;
char a[1010][1010];
ll dp[1010][1010] = {};
int main() {
	cin >> H >> W;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> a[i][j];
		}
	}
	dp[0][0] = 1;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			if (a[i][j] == '#')continue;
			dp[i + 1][j] += dp[i][j];
			dp[i + 1][j] %= INF;
			dp[i][j + 1] += dp[i][j];
			dp[i][j + 1] %= INF;
		}
	}
	cout << dp[H - 1][W - 1] << endl;
	return 0;
}
```
a[I][j]=='#'の時continueにするのは頭いいな

I

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
	int N;
	cin >> N;
	vector<double>P(N);
	for (int i = 0; i < N; ++i)cin >> P[i];
	double dp[3100][3100];
	//dp[i][j]:=最初のi枚のコインを投げた時に表がj枚となる確率
	//とすると緩和式は次のコインが表の時:dp[i+1][j+1]+=dp[i][j]*p
	//次のコインが裏の時:dp[i+1][j]+=dp[i][j]*(1-p)となります
	dp[0][0] = 1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			dp[i + 1][j + 1] += dp[i][j] * P[i];
			dp[i + 1][j] += dp[i][j] * (1 - P[i]);
		}
	}
	double res = 0.0;
	for (int j = (N + 1) / 2; j <= N; ++j)res += dp[N][j];
	cout << fixed << setprecision(10) << res << endl;
	return 0;
}
```

J

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int N;
double dp[310][310][310];
//dp[i][j][k]で寿司が3個の皿がi枚、２個の皿がj枚、3個の皿がk枚ある
//状態から寿司を全てなくすのに必要な操作回数の期待値
//次に残0枚の皿を引く確率はN-i-j-k/N,行先はdp[i][j][k]
//残1枚の皿を引く確率はi,行先はdp[i-1][j][k]
//残2枚の皿を引く確率はj,行先はdp[i+1][j-1][k]
//残3枚の皿を引く確率はk,行先はdp[i][j+1][k-1]
//期待値漸化式はdp[i][j][k]=(dp[i][j][k]*(N-i-j-k)/N+dp[i-1][l][k]*i/N+dp[i+1][j-1][k]*j/N+dp[i][j+1][k-1]*k/N)+1;
//これを変形して自己ループを除去すると
//dp[i][j][k]=(dp[i-1][[j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k+N)*1/i+j+k;
double rec(int i, int j, int k) {
	if (dp[i][j][k] >= 0)return dp[i][j][k];
	if (i == 0 && j == 0 && k == 0) {
		return 0.0;
	}
	double res = 0.0;
	if (i > 0)res += rec(i - 1, j, k)*i;
	if (j > 0)res += rec(i + 1, j - 1, k)*j;
	if (k > 0)res += rec(i, j + 1, k - 1)*k;
	res += N;
	res *= 1.0 / (i + j + k);
	return dp[i][j][k] = res;
}
int main() {
	cin >> N;
	int one = 0, two = 0, three = 0;
	for (int i = 0; i < N; ++i) {
		int a; cin >> a;
		if (a == 1)++one;
		else if (a == 2)++two;
		else ++three;
	}
	memset(dp, -1, sizeof(dp));
	cout << fixed << setprecision(10) << rec(one, two, three) << endl;
	return 0;
}

```
K
dp[k]:=k個の石からなる山で先手が勝ち状態か（＝１なら勝ち状態）
後退解析の基本は、「全てが勝ち状態なら負け状態。遷移先に１つでも負け状態があるなら勝ち状態」である。
あるdp[k]について、遷移先は１００通りあるのでこのすべてをみて負け状態が１つでもあれば勝ち状態にする。注意すべきなのは、遷移することができない場合は操作を行えないということなので負け状態とすること

```#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int N;
int K, a[110];
int dp[111111];
int main() {
	cin >> N >> K;
	for (int i = 0; i < N; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < K + 1; ++i) {
		int lose = 0, cnt = 0;
		for (int j = 0; j < N; ++j) {
			//操作を行えるかどうか調べる
			//操作を行えないなら負け
			if (0 <= i - a[j]) {
				cnt++;//cntが1以上なら操作を行える
				if (!dp[i-a[j]])lose++;//もし相手を負け状態にできる選択肢があるなら
				//選んで相手を負け状態にする。
			}
		}
		if (cnt == 0)dp[i] = 0;
		else if (0 < lose)dp[i] = 1;
		else dp[i] = 0;//遷移先が全て勝ち状態なら負け状態
	}
	if (dp[K])cout << "First" << endl;
	else cout << "Second" << endl;
	return 0;
}
```
あったまいいー こういうのgrundy数っていうらしい？

L
メモ化再帰

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
ll memo[3001][3001][2];
int a[3000];
//f(a,b,c)で左端がa,右端がbの時のX-Yを返す。c=0の時太郎の番1の時次郎の番
ll f(int l, int r, int state) {
	if (l > r)return 0;
	if (memo[l][r][state] !=0)return memo[l][r][state];
	ll ret = 0;
	if (state == 0) {
		ret = max(f(l + 1, r, 1) + a[l], f(l, r - 1, 1) + a[r]);
	}
	else {
		ret = min(f(l + 1, r, 0) - a[l], f(l, r - 1, 0) - a[r]);
	}
	return  memo[l][r][state] = ret;
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	cout << f(0, n - 1, 0) << endl;
	return 0;
}
```