题解 | #Kevin的宝石#

和题解的DP方法不一样，,代表前i个宝石考虑完了之后剩下j块钱的最大价值

考虑对于普通宝石 =

然后考虑魔法宝石对于每种魔法宝石，可以考虑与前面的魔法宝石发生碰撞位置L和位置R的魔法宝石发生碰撞情况只有这个区间内的魔法宝石数量是偶数，且L和R都是魔法宝石，那么就可以从内到外的不断碰撞，直到最后L和R位置的宝石发生碰撞，区间能发生碰撞的话，能够获得的权值也是固定的，就是区间内普通宝石的权值，区间能发生碰撞的话，所消耗的钱也是固定的，就是区间内魔法宝石的权值。 区间内普通宝石的权值前缀和，区间内魔法宝石的权值前缀和 在位置R是魔法宝石时的转移为,满足上述要求, 这就是转移式子，后面是分析偶数个魔法宝石的问题，设置一个前缀和记录一下现在是奇数个魔法宝石还是偶数个魔法宝石，如果有偶数个魔法宝石，有偶数个魔法宝石，那么就有偶数个。如果有奇数个魔法宝石，有奇数个魔法宝石，那么就有偶数个。 借助两个map用来分奇偶就可以完成转移。 复杂就是多了一个log

int N, K;
bool OP[max_];
ll sum[3][max_];
struct {
	int op, val;
}node[max_];
map<ll, ll>mp[2];
ll f[max_];
void clear() { mp[0].clear(); mp[1].clear(); }
void solve() {
	int i, j;
	N = read(); K = read();
	for (i = 1; i <= N; i++) {
		node[i].op = read();
		node[i].val = read();
		if (node[i].op == 1) {
			sum[1][i] = sum[1][i - 1] + (ll)node[i].val;
			sum[2][i] = sum[2][i - 1];
		}
		else {
			sum[2][i] = sum[2][i - 1] + (ll)node[i].val;
			sum[1][i] = sum[1][i - 1];
		}
		OP[i] = OP[i - 1] ^ (node[i].op == 2);
	}
	if (node[1].op == 2)
		mp[0][K] = 0;
	for (j = 0; j <= K; j++)f[j] = -INF;
	f[K] = 0;
	int t1, ans = 0;;
	for (i = 1; i <= N; i++) {
		if (node[i].op == 2)
			for (j = 0; j <= K; j++) {
				if (mp[OP[i]].find(j + sum[2][i]) != mp[OP[i]].end()) {
					f[j] = max(f[j], mp[OP[i]][j + sum[2][i]] + sum[1][i]);
				}
				ans = max(ans, f[j]);
			}
		if (node[i + 1].op == 2)
			for (j = 0; j <= K; j++) {
				if (f[j] == -INF)continue;
				if (mp[OP[i]].find(j + sum[2][i]) != mp[OP[i]].end()) {
					t1 = mp[OP[i]][j + sum[2][i]];
					mp[OP[i]][j + sum[2][i]] = max(t1, f[j] - sum[1][i]);
				}
				else mp[OP[i]][j + sum[2][i]] = f[j] - sum[1][i];
			}
	}
	printf("%lld\n", ans);
}