Educational Codeforces Round 57 D. Easy Problem(DP?)
4607 ワード
タイトル:https://codeforces.com/contest/1096/problem/D
とても面白い問題です.
リュックサックのように見えますが、サブシーケンスというものは、順番を保証しなければならないので、実は秩序ある01リュックサックです.
秩序あるリュックサックは、4文字しかなく、複雑さを線形に下げることができ、スキャンしても、各文字の「取るか取らないか」で行えます.
とても面白い問題です.
リュックサックのように見えますが、サブシーケンスというものは、順番を保証しなければならないので、実は秩序ある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;
}