dp練習

文字列dp
AGC 037 a

ARC 075-A

```
#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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int main() {
	int N;
	int s[110];
	int dp[110][10010];//dp[i][j]でi回目の操作の時に和がjとなりえるか
	cin >> N;
	for (int i = 0; i < N; ++i)cin >> s[i];
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= 10000; ++j) {
			if (dp[i][j] == 0)continue;
			dp[i + 1][j] = 1;
			dp[i + 1][j + s[i]] = 1;
		}
	}
	int ans = 0;
	for (int i = 0; i <= 10000; ++i) {
		if (dp[N][i] == 1) {
			if (i % 10 != 0) {
				ans = max(ans, i);
			}
		}
	}
	cout << ans << endl;
	return 0;
}
```

abc118-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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
const string MINUSINF = "-";

void chmax(string &a, string b) {
	if (a == MINUSINF)a = b;
	else if (a.size() < b.size())a = b;
	else if (a.size() == b.size()) {
		if (a < b)a = b;
	}
}//&を付けることで変数を書き換えられるよ！

ll match[10] = { 2,5,5,4,5,6,3,7,6 };
string dp[11000];//dp[N]でマッチをN本使ってできる数値の最大値
int main() {
	int N, M; cin >> N >> M;
	vector<int>A(M);
	for (int i = 0; i < M; ++i)cin >> A[i];
	for (int i = 0; i < 11000; ++i) {
		dp[i] = MINUSINF;
	}
	dp[0] = "";
	for (int i = 0; i <= N; ++i) {
		if (dp[i] == MINUSINF)continue;
		for (auto a : A) {
			chmax(dp[i + match[a - 1]], dp[i] + (char)('0' + a));
		}
	}
	cout << dp[N] << endl;
	return 0;
}
```


015-D
https://atcoder.jp/contests/abc015/tasks/abc015_4

```
#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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
int W, N, K;
int A[55], B[55];
int dp[55][55][10010];//dp[i][j][w]:=i番目までからj個選んだ時の幅合計w以下での最大の価値
int main() {
	cin >> W >> N >> K;
	for (int i = 0; i < N; ++i) {
		cin >> A[i] >> B[i];
	}
	REP(i, 55)REP(j, 55)REP(k, 10010)dp[i][j][k] = -1;
	dp[0][0][0] = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= K; ++j) {
			for (int k = 0; k <= W; ++k) {
				if (dp[i][j][k] == -1)continue;
				if (j == K) {//枚数的にもう足りない
					dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
				}
				else {
					if (k + A[i] <= W) {//幅が足りる
						dp[i + 1][j + 1][k + A[i]] = max(dp[i + 1][j + 1][k + A[i]], dp[i][j][k] + B[i]);
						dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
					}
					else {//幅が足りない
						dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
					}
				}
			}
		}
	}
	int ans = 0;
	for (int j = 0; j < 55; ++j) {
		for (int k = 0; k < 10010; ++k) {
			ans = max(ans, dp[N][j][k]);
		}
	}
	cout << ans << endl;
	return 0;
}
```
ナップサック応用版。

てぃぴかるでぃーぴぃーコンA
https://tdpc.contest.atcoder.jp/tasks/tdpc_contest

```
#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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
int N;
int p[110];
bool dp[110][10010];//dp[x][y]でx問目までで総合点yになりえるか
int main() {
	cin >> N;
	REP(i, N)cin >> p[i];
	fill_n(*dp, 110 * 10010, false);
	dp[0][0] = true;
	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j < 10010; ++j) {
			if (j < p[i - 1] || dp[i - 1][j]) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = dp[i - 1][j - p[i-1]];
			}
		}
	}
	int count = 0;
	for (int i = 0; i <= 10000; ++i) {
		if (dp[N][i])count++;
	}
	cout << count << endl;
	return 0;
}
```

dpコン　D-サイコロ
https://tdpc.contest.atcoder.jp/tasks/tdpc_dice
サイコロの出た目の積の素因数には 2, 3, 5 しかない．
つまり，D にそれ以外の素因数があればダメ．
そうでなければ，D = 2^a * 3^b * 5^c と一意的に表すことができる．
dp[x][y][z] := 今現在，2の素因数が x 個，3 の素因数が y 個，5 の素因数が z 個となる確率
というDPテーブルを考えれば，そこからもう一つサイコロを投げた時の遷移が書ける
漸化式の定義は

```
dp[n+1][i][j][k]+=1/6*dp[n][i][j][k](１の目が出た時)
dp[n+1][i+1][j][k]+=1/6*dp[n][i][j][k](2の目が出た時)
dp[n+1][i][j+1][k]+=1/6*dp[n][i][j][k](3の目が出た時)
dp[n+1][i+2][j][k]+=1/6*dp[n][i][j][k](4の目が出た時)
dp[n+1][i][j][k+1]+=1/6*dp[n][i][j][k](5の目が出た時)
dp[n+1][i+1][j+1][k]+=1/6*dp[n][i][j][k](6の目が出た時)
```

dp[n][i][j][k]:サイコロをn回振ったとき出た目の積が2^i*3^j*5^kと表される確率
(0<=n<=N,0<=i<=I,0<=j<=J,0<=k<=K)
初期値:dp[0][0][0][0]=1
求める解:dp[n][i][j][k]
//d2:=Dを素因数分解したときに登場する2の個数とした時、
i>=d2,j>=d3,k>=d5となるi,j,kを選んだ時のdp[N][i][j][k]の総和
n回目でi,j,kがそれぞれd2,d3,d5にたどり着いた時点でそれ以降は1~6のどの目がでても問題の条件を満たすということに着目すると

```
dp[n+1][i][j][k]+=dp[n][i][j][k]/6
dp[n+1][min(i+1,d2)][j][k]+=dp[n][i][j][k]/6
dp[n+1][i][min(j,d3)][k]+=dp[n][i][j][k]/6
dp[n+1][min(i+2,d2)][j][k]+=dp[n][i][j][k]/6
dp[n+1][i][j][min(k+1,d5)]+=dp[n][i][j][k]/6
dp[n+1][min(i+1,d2)][min(j+1,d3)][k]+=dp[n][i][j][k]/6
```
と書き直せる。

```
#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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
ll N;
ll D;
int memo[6] = { 0 };
double dp[101][64][40][30] = { 0 };
int main() {
	cout << fixed << setprecision(10);
	cin >> N >> D;
	for (int i = 2; i < 6; ++i) {
		while (D%i == 0) {
			++memo[i];
			D /= i;
		}
	}
	if (D > 1) {
		cout << 0.0 << endl;
		return 0;
	}
	dp[0][0][0][0] = 1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= min(2 * (i + 1), memo[2]); ++j) {
			for (int k = 0; k <= min(i + 1, memo[3]); ++k) {
				for (int l = 0; l <= min(i + 1, memo[5]); ++l) {
					// 1
					dp[i + 1][j][k][l] += dp[i][j][k][l] / 6;
					// 2

					dp[i + 1][min(j + 1, memo[2])][k][l] +=
						dp[i][j][k][l] / 6;
					// 3
					dp[i + 1][j][min(k + 1, memo[3])][l] +=
						dp[i][j][k][l] / 6;
					// 4
					dp[i + 1][min(j + 2, memo[2])][k][l] +=
						dp[i][j][k][l] / 6;
					// 5
					dp[i + 1][j][k][min(l + 1, memo[5])] +=
						dp[i][j][k][l] / 6;
					// 6
					dp[i + 1][min(j + 1, memo[2])]
						[min(k + 1, memo[3])][l] += dp[i][j][k][l] / 6;
				}
			}
		}
	}
	cout << dp[N][memo[2]][memo[3]][memo[5]] << endl;
	return 0;
}
```
ARC057-B
https://arc057.contest.atcoder.jp/tasks/arc057_b

dp[i][j]=(i日目までにj回機嫌が良くなるようにするために必要な最低限の勝ち数)とすると、i日目は機嫌を良くしないとすると全敗するのが最適。i日目を機嫌よくするとすると最低限勝つのが最適。
これでdp[N][ans]<=Kとなる最大のansを最後に確認すれば良い

```
#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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
int A[2200];
int N, K;
ll dp[2222][2222];
//dp[i][j]=(i日目までにj回機嫌がよくなるようにするために必要な最低限の勝ち数）
int sum[2222];//i回目までにゲームをした総数
int main() {
	cin >> N >> K;
	sum[0] = 0;
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
		sum[i+1] = sum[i] + A[i];
	}
	if (sum[N] == K) {
		cout << 1 << endl;
		return 0;
	}
	for (int i = 0; i <= N; ++i)for (int j = 0; j <= N; ++j)dp[i][j] = INF;
	dp[0][0] = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= i; ++j) {
			if (dp[i][j] < INF) {//勝たない
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
			}
			if (i == 0) {//勝つ
				dp[i + 1][j + 1] = min(dp[i+1][j+1],dp[i][j]+1);
			}
			else {
				ll atleast = dp[i][j] * sum[i + 1] / sum[i] + 1;
				if (atleast <= A[i] + dp[i][j]) {
					dp[i + 1][j + 1] = min(dp[i + 1][j + 1], atleast);
				}
			}
		}
	}
	for (int i = N; i >= 0; --i) {
		if (dp[N][i] <= K) {
			cout << i << endl;
			break;
		}
	}
	return 0;
}
```
時間くわれまくった

typical dp 02 ゲーム
ゲームでお互いが最善を尽くした時という問題はどちらか片方のプレイヤー側からみた場合の状態を考えるとうまくいくことが多い。ある状態でのその時以降に先手がとれるものの価値の合計を考える。
先手がとる番の時は左右の山どちらかの物をとった後の状態から得られる価値の合計がわかっていれば今からとるものと、取った後の状態から得られる価値の和が大きくなるようにとる。
後手が取る番の時はその状態で先手が得られる価値の合計になる。後手が取っても先手の合計は増えないので。従って後手が最善を尽くすということは先手にとって最悪なので取った後に先手が得られる価値が少なくなるように取る。

先手の番か後手の番かはこれまでに取った物の数(A+B-(i+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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////
int a, b;
int A[1024], B[1024];
int main() {
	cin >> a >> b;
	for (int i = 0; i < a; ++i)cin >> A[i];
	for (int i = 0; i < b; ++i)cin >> B[i];
	//dp[i][j]=Aがi個、Bからj個取った状態から最後までの
	//先行の最適スコア
	vector<vector<int>>dp(a + 1, vector<int>(b + 1));
	//最終状態の値を0にする
	dp[a][b] = 0;
	//逆順にループしてDPテーブルを埋める
	for (int i = a; i >= 0; --i) {
		for (int j = b; j >= 0; --j) {
			if (i == a && j == b)continue;
			if ((i+j) % 2 == 0) {
				//先攻番
				if (i == a) {
					dp[i][j] = B[j] + dp[i][j + 1];
				}
				else if (j == b) {
					dp[i][j] = A[i] + dp[i + 1][j];
				}
				else {
					dp[i][j] = max(A[i] + dp[i+1][j], B[j] + dp[i][j +1]);
				}
			}
			else {//後攻番
				if (i == a) {
					dp[i][j] = dp[i][j + 1];
				}
				else if (j == b) {
					dp[i][j] = dp[i + 1][j];
				}
				else {
					dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]);
				}
			}
		}
	}
	cout << dp[0][0] << endl;
	return 0;
}
```
二問目の難易度ちゃう、、

typical dp 05
N 以下の正整数であって、十進法表記したときの各桁の数の和が D の倍数であるものの個数を mod 1,000,000,007 で求めよ。

桁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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
string N;
int D;
int main() {
	cin >> D >> N;
	int n = N.size();
	vector<vector<vector<ll>>>dp(n + 1, vector<vector<ll>>(D, vector<ll>(2)));
	dp[0][0][0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < D; ++j) {
			for (int k = 0; k < 2; ++k) {
				int x = k ? 9 : N[i] - '0';
				for (int d = 0; d <= x; ++d) {
					Add(dp[i + 1][(j + d) % D][d<x||k],dp[i][j][k] );
				}
			}
		}
	}
	ll ans = 0;
	for (int j = 0; j < 2; ++j) {
		Add(ans, dp[n][0][j]);
	}

	cout << ans-1 << endl;
	return 0;
}
```
例題ABC007-D https://abc007.contest.atcoder.jp/tasks/abc007_4

```
#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 A, B;
ll dp[30][2][2];
ll solve(string S) {
	const int N = S.size();
	memset(dp, 0, sizeof(dp));
	dp[0][0][0] = 1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k < 2; ++k) {
				int x = j ? 9 : S[i] - '0';
				for (int d = 0; d <= x; ++d) {
					dp[i + 1][j || d < x][k || d == 4 || d == 9] += dp[i][j][k];
				}
			}
		}
	}
	return dp[N][0][1] + dp[N][1][1];
}
int main() {
	cin >> A >> B;
	cout << solve(to_string(B)) - solve(to_string(A - 1)) << endl;
	return 0;
}
```
これの解説はbitのところで書いた。
abc 129 E

```
#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<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int main() {
	string L;
	cin >> L;
	ll dp[100100][2];
	memset(dp, 0, sizeof(dp));
	//dp[i][j]:=上からi行目までを決めてその桁までが(0,0),(0,1),(1,0)の3通りから選ばれていて
	//a+bがLより小さいことが確定している(j=1)/いない(j=0)ような選び方の個数
	int n = L.size();
	dp[0][0] = 1;
	for (int i = 0; i < n; ++i) {
			dp[i + 1][1] += dp[i][1] * 3;
			if (L[i] == '1') {
				dp[i + 1][1] += dp[i][0];
				dp[i + 1][0] += dp[i][0] * 2;
			}
			else {
				dp[i + 1][0] += dp[i][0];
			}
			dp[i + 1][0] %= INF;
			dp[i + 1][1] %= INF;
	}
	ll ans = dp[n][1] + dp[n][0];
	ans %= INF;
	cout << ans << endl;
	return 0;
}
```
一応桁dpがテーマっぽかったがあまり桁感はない気がした

abc006-D
トランプ挿入ソート
数字が書かれたカードがN枚あります。このカードの束（山札）に対して以下の操作が可能です。
山札からカードを 1枚抜き取り、任意の場所に挿入する。
山札の上から下に向けて、カードを昇順に並べ替えるために必要な、最小の操作回数を求めてください。

抜き取らないトランプに注目すると、それらは増加数列になっているはずなので、最長増加部分列を求めて全体から引いた数が答え。

```
#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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
ll N;
ll C[210000];
ll dp[210000];
ll solve() {
	for (int i = 0; i < N; ++i)dp[i] = INF;
	for (int i = 0; i < N; ++i) {
		int it = lower_bound(dp, dp+N, C[i]) - dp;
		dp[it] = C[i];
	}
	int res = 0;
	for (int i = 0; i < N; ++i) {
		if (dp[i] < INF)++res;
	}
	return N - res;
}
int main() {
	cin >> N;
	for (int i = 0; i < N; ++i)cin >> C[i], C[i]--;
	cout << solve() << endl;
	return 0;
}
```
abc038-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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int lis(vector<int>a) {
	int n = a.size();
	vector<int>dp(n, INF);
	for (int i = 0; i < n; ++i) {
		*lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
	}
	return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}
int main() {
	int n;
	cin >> n;
	vector<pii>a(n);
	for (int i = 0; i < n; ++i) {
		int w, h;
		cin >> w >> h;
		a[i].first = w;
		a[i].second = -h;
	}
	sort(a.begin(), a.end());
	REP(i, n)a[i].second *= -1;
	vector<int>b(n,INF);
	REP(i, n) {
		*lower_bound(b.begin(), b.end(), a[i].second) = a[i].second;
	}
	cout << lower_bound(b.begin(),b.end(),INF)-b.begin() << endl;
	return 0;
}
```
hを降順にしてソートするのがミソ
abc 025-c
双子とoxゲーム

```
#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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
int masu[3][3];
int b[2][3];
int c[3][2];
int total;
int calc(void) {
	int ret = 0;//直大くんが取得する点数
	REP(i, 2)REP(j, 3) {
		if (masu[i][j] == masu[i + 1][j]) {
			ret += b[i][j];
		}
	}
	REP(i, 3)REP(j, 2) {
		if (masu[i][j] == masu[i][j + 1]) {
			ret += c[i][j];
		}
	}
	return ret;//直大の点数
}

int dfs(int turn) {
	if (turn == 9) {
		return calc();
	}
	int ret = (turn % 2 == 0) ? -INF : INF;
	REP(i, 3)REP(j,3) {
		if (masu[i][j] == -1) {
			masu[i][j] = (turn % 2 == 0) ? 1 : 0;
			ret = (turn % 2 == 0) ? max(ret, dfs(turn + 1)) : min(ret, dfs(turn + 1));
			masu[i][j] = -1;
		}
	}
	return ret;
}
int main() {
	total = 0;
	REP(i, 3)REP(j, 3) masu[i][j] = -1;
	REP(i, 2)REP(j, 3) {
		cin >> b[i][j];
		total += b[i][j];
	}
	REP(i, 3)REP(j, 2) {
		cin >> c[i][j];
		total += c[i][j];
	}
	int ans = dfs(0);
	cout << ans << endl;//直大の点数
	cout << total - ans << endl;//直子の点数
	return 0;
}
```
ゲームdpむずい、、

ARC085-C

```
ll N, Z, W;
vector<ll>a;
int main() {
	cin >> N >> Z >> W;
	a.resize(N);
	REP(i, N)cin >> a[i];
	if (N == 1) {
		cout << abs(a[0] - W) << endl;
	}
	else {
		cout << max(abs(a[N - 1] - W), abs(a[N - 1] - a[N - 2])) << endl;
	}

	return 0;
}
```
ゲーム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<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T1, class T2> void chmin(T1 &a, T2 b) { if (a>b)a = b; }

template<class T1, class T2> void chmax(T1 &a, T2 b) { if (a<b)a = b; }
template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////
ll N, Z, W;
ll a[10001];
ll dp[5100][3];
ll rec(int cur, bool sente) {
	if (dp[cur][sente] != -1)return dp[cur][sente];
	ll aite = -1;
	if (cur == 0)aite = W;
	else aite = a[cur - 1];
	if (cur == N - 1)return abs(a[N - 1] - aite);
	ll res = -1;
	if (sente) {
		ll Max = abs(aite - a[N - 1]);
		for (int j = cur; j < N - 1; ++j) {
			ll tmp = rec(j + 1, false);
			chmax(Max, tmp);
		}
		res = Max;
	}
	else {
		ll Min = abs(aite - a[N - 1]);
		for (int j = cur; j < N - 1; ++j) {
			ll tmp = rec(j + 1, true);
			chmin(Min, tmp);
		}
		res = Min;
	}
	return dp[cur][sente] = res;
}
int main() {
	cin >> N >> Z >> W;
	REP(i, N)cin >> a[i];
	memset(dp, -1, sizeof(dp));
	cout << rec(0, true) << endl;
	return 0;
}
```
うーんむずい、、
typical dp　I イゥイ
区間dp
dp[l][r]:[l,r)で最大何文字取り除けるかと定義する
まずdp[l][r]=max(dp[l][I]+dp[I][r])(I=l,,,,r)という変形は明らかあとはs[l...r)が完全に取り除ける場合そこから端をくっつけるかを確認する。
例えば"iiwiwi"ならばs[1...4)が"iwi"で、端に"I"+"wi"をくっつけられる。iwiは3文字なのでくっつけられるかどうかは普通に調べる

```
#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<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////
//dp[l][r]:=[l,r)で最大何文字取り除けるかと定義する
//まずdp[l][r]=max(dp[l][i]+dp[i][r])(i=l,,,r)という遷移は明らかだと思う
//あとは,s[l,,,r)が完全に取り除ける(つまりdp[l][r]==r-l)場合そこから端に"iwi"を
//くっつけられるかを確認する例えば"iiwiwi"ならs[1....4)が"iwi"で端に"i"+"wi"をくっつけられる
//iwiは3文字なのでくっつけられるかは普通に全部調べたらいい
int main() {
	string s; cin >> s;
	int const n = s.size();
    //[l,r)
	vector<vector<int>>dp(n + 1, vector<int>(n + 1, 0));
	for (int w = 0; w <= n; ++w) {
		for (int l = 0; l+w <= n; ++l) {
			for (int i = l; i <= l + w; ++i) {
				dp[l][l + w] = max(dp[l][l + w], dp[l][i] + dp[i][l + w]);
			}
			if (dp[l][l + w] != w) {
				continue;
			}
			for (int d = 0; d <= 3; ++d) {
				if (l - d < 0 || n < l + w + 3 - d) {
					continue;
				}
				auto iwi = s.substr(l - d, d) + s.substr(l + w, 3 - d);
				if (iwi == "iwi") {
					dp[l - d][l + w + 3 - d] = dp[l][l + w] + 3;
				}
			}
		}
	}
	int res = 0;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			res = max(dp[i][j], res);
		}
	}
	res /= 3;
	cout << res << endl;
	return 0;
}
```

区間分割dp
agc 031 B reversi
dpの形としては多くの場合
.dp[i]:=左からi個のところでちょうど区切る場合について、左からi個分についての値
として遷移を考えるときは前回どこで区切ったのかを場合分けする。前回の区切りをjとすると
.dp[i]+=dp[j]+(何か)
.chmax(dp[i],dp[j]+(何か))
といった遷移式が立つ。
そして何も工夫しないと多くの場合o(N**2)になるので問題に応じて様々な高速化を考えることになる。
・Jの候補が高々数通りしか考えなくてよい、累積和、セグ木などで

今回は最初の見方でやる。
特徴として言えることは二つある。
.区間に対する操作である
.過去の履歴をすべて破壊して上書きしてしまう操作である。
二つ目の特徴から、交差している二つの区間に対して操作を行うことはないものとしてよいことからこの問題は区間ごとに分割する問題に見えてくる
今回はdp[i]+=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<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { -1, 0, 0, 1 };
const ll dy[4] = { 0, -1, 1, 0 };
const ll INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
struct Accelerate_Cin {
	Accelerate_Cin() {
		cin.tie(0);
		ios::sync_with_stdio(0);
		cout << fixed << setprecision(20);
	};
};
///////////////////////////////////////

vector<int> places[210000];
ll dp[210000];
void add(ll &a, ll b) { a += b; if (a >= INF)a -= INF; }

int main() {
	//入力
	int N; cin >> N;
	vector<int>c(N);
	for (int i = 0; i < N; ++i)cin >> c[i];
	//places[i]:=(c[j]=iとなるようなjの集まり)
	for (int i = 0; i < 210000; ++i)places[i].clear();
	for (int i = 0; i < N; ++i)places[c[i]].push_back(i);
	//DP
	dp[0] = 1;
	for (int i = 1; i <= N; ++i) {
		//特に操作しない場合
		add(dp[i], dp[i - 1]);
		//操作する場合
		int color = c[i - 1];
		int it = lower_bound(places[color].begin(), places[color].end(), i - 1) - places[color].begin();
		//c[i]がcolor色の何番目の要素か
		if (it > 0) {
			int j = places[color][it - 1];//c[j]=c[i]となるj
			if ((i - 1) - j > 1)add(dp[i], dp[j + 1]);
		}
	}
	cout << dp[N] << endl;
	return 0;
}
```