Educational Codeforces Round 57 D. Easy Problem(DP?)

4607 ワード

タイトル:https://codeforces.com/contest/1096/problem/D
とても面白い問題です.
リュックサックのように見えますが、サブシーケンスというものは、順番を保証しなければならないので、実は秩序ある01リュックサックです.
秩序あるリュックサックは、4文字しかなく、複雑さを線形に下げることができ、スキャンしても、各文字の「取るか取らないか」で行えます.
#include 
using namespace std;

string s;
long long n, a, b, c, d;

int main() {
	cin >> n >> s;

	for(int i = 0; i < n; i++) {
		int h;
		cin >> h;
		if(s[i] == 'h') {
			a += h;
		} else if(s[i] == 'a') {
			b = min(a, b + h);
		} else if(s[i] == 'r') {
			c = min(b, c + h);
		} else if(s[i] == 'd') {
			d = min(c, d + h);
		}
	}
	cout << d;
	return 0;
}