abc 104　C dp,bit探索 D dp

C
わからん

dp

```
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
const int INF = 1e8;
ll D, G;
ll dp[12][1201];//i番目の問題まで見て、合計j個の問題をすでに解いている際における総合スコアの最大値
int main() {
	cin >> D >> G;
	vector<ll>P(D + 1), C(D + 1);
	for (int i = 1; i <= D; ++i) {
		cin >> P[i] >> C[i];
	}
	for (int i = 1; i <= D; ++i) {
		for (int j = 0; j <= 1010; ++j) {
			for (int k = 0; k <= P[i]; ++k) {
				if (k == P[i]) {
					dp[i][j + k] = max(dp[i][j + k], dp[i-1][j] + 100 * i*k + C[i]);
				}
				else {
					dp[i][j + k] = max(dp[i][j + k], dp[i-1][j] + 100 * i*k);
				}
			}
		}
	}
	for(int j = 0; j < 1010; ++j) {
		if (dp[D][j] >= G) {
			cout << j << endl;
			break;
		}
	}
	return 0;
}
```
ある値より大きくなるための最小個数をもとめるには、ある個数での最大値がその値より大きくなる時の個数を求めればよい。なんかへんな説明だな

bitで解く

0 & 0 → 0
0 & 1 → 0
1 & 0 → 0
1 & 1 → 1

0 | 0 → 0
0 | 1 → 1
1 | 0 → 1
1 | 1 → 1

&　→　論理積
|　→　論理和
^　→　排他的論理和
~ →　　否定演算

論理積は、2つのビットを比べて、どちらも1なら１とし、どちらかが0なら0とする、演算方式です。
論理和は、2つのビットを比べて、どちらも1なら１とし、どちらかが１なら１とする、演算方式です。
排他的論理和は、2つのビットを比べて、同じ値なら０とし、片方だけ１ならば１とする、演算方式です。
否定演算は、あるビットが０なら１にし、あるビットが１なら０にする、計算方式です。

```
#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 D;
ll G;
vector<ll>p, c;
int main() {
	cin >> D >> G;
	p.resize(D); c.resize(D);
	for (int i = 0; i < D; ++i) {
		cin >> p[i] >> c[i];
	}
	ll res = 1 << 29;//全完する難易度帯を2^D通り固め打ちする
	for (int bit = 0; bit < (1 << D); ++bit) {
		ll sum = 0;
		ll num = 0;
		for (int i = 0; i < D; ++i) {
			if (bit & (1 << i)) {
				sum += c[i] + p[i] * 100 * (i + 1), num += p[i];
			}
		}
		if (sum >= G)res = min(res, num);
		else {
			for (int i = D - 1; i >= 0; --i) {
				if (bit&(1 << i))continue;
				for (int j = 0; j < p[i]; ++j) {
					if (sum >= G)break;
					sum += 100 * (i + 1);
					++num;
				}
			}
			res = min(res, num);
		}
	}
	cout << res << endl;
	return 0;
}
```
これはいい問題だわいや
D
WE LOVE ABC
dpをしよう
dp[I+1][0]:=I文字目まで考えたときにABCとの照合をスタートすらしていないようなものの個数
dp[I+1][1]:=I文字目まで考えた時にABCとの照合においてAまでは照合させたものの個数
dp[I+1][2]:=I文字目まで考えたときにABCとの照合においてBまでは照合させたようなものの個数
dp[I+1][3]:=I文字目まで考えた時にABCとの照合においてCまでは照合させたようなものの個数
という感じでDPを定義した。
初期値：dp[0][0]=1
求める値:dp[S.size()][3]
I文字目でABCカウントを進めない場合
I文字目が'?'だった場合は３文字あるのでdp[I+1][j]+=dp[I][j]*3
I文字目が'?'以外だったらdp[I+1][j]+=dp[I][j]

I文字目でABCカウントを進める場合
I文字目が'A'または'?'だった場合は「なし」から「A」にカウンタを勧められるので
dp[I+1][1]+=dp[I][0]

```
#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;
string s;
void add(ll &a, ll b) {
	a += b;
	if (a >= INF)a -= INF;
}
ll dp[210000][5];//dp[i+1][3]:=i文字目まで考えた時にABCとの
//照合においてCまでは照合させたようなもの
int main() {
	cin >> s;
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for (int i = 0; i < s.size(); ++i) {
		for (int j = 0; j < 5; ++j) {
			if (s[i] != '?')add(dp[i + 1][j], dp[i][j]);
			else add(dp[i + 1][j], dp[i][j] * 3 % INF);
		}
		if (s[i] == 'A' || s[i] == '?')add(dp[i + 1][1], dp[i][0]);
		if (s[i] == 'B' || s[i] == '?')add(dp[i + 1][2], dp[i][1]);
		if (s[i] == 'C' || s[i] == '?')add(dp[i + 1][3], dp[i][2]);
	}
	cout << dp[s.size()][3] << endl;
	return 0;
}
```
I文字目が'B'または'?'だった場合は「A」から「B」にカウンタを勧められるので
dp[I+1][2]+=dp[I][1]
I文字目が'C'または'?'だった場合は「B」から「C」にカウンタを勧められるので
dp[I+1][3]+=dp[I][2]