Untitled

mail@pastecode.io avatar
unknown
c_cpp
a month ago
587 B
2
Indexable
Never
int dp[N]; // N = 200200 though max n is 1000
vector<int> steps = {1, 3, 5};
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    // std::freopen("lepus.in", "r", stdin);
    // std::freopen("lepus.out", "w", stdout);
    memset(dp, -1, sizeof(dp));
    int n; cin >> n;
    string s; cin >> s;
    s = '#' + s; 
    dp[1] = 0;
    for(int i = 1; i <= n; ++i){
    	if(s[i] != 'w'){
    		for(auto x : steps){
    			if(i >= x && s[i - x] != -1){
    				dp[i] = max(dp[i], dp[i - x] + (s[i] == '"'));
    			}	
    		}
    	}
    }
    cout << dp[n];
    return 0;
}
Leave a Comment