ferinの競プロ帳

競プロについてのメモ

東京工業大学プログラミングコンテスト2015 F - レシート

競技プログラミング AtCoder

問題ページ

i桁目で一致する状況

  • 下の桁で繰り下がりがない && X[i]=0 && A[i]=0
  • 下の桁で繰り下がりがある && X[i]=9 && A[i]=9

dp[下からi桁目][下の桁で繰り下がりが発生したか？」 という DPテーブルを持ち，以下の遷移を行う．

  • chmax(dp[i+1][0], max(dp[i][0], dp[i][1])) 任意の場合でok
  • chmax(dp[i+1][1], max(dp[i][0], dp[i][1])) 任意の場合でok
  • chmax(dp[i+1][0], dp[i][0]+1) A[i]='0'のみ
  • chmax(dp[i+1][1], dp[i][1]+1) A[i]='9'のみ
#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    string s;  
    cin >> s;  
    reverse(ALL(s));  
    ll n = s.size();  
  
    vector<vector<ll>> dp(n+1, vector<ll>(2, -INF));  
    dp[0][0] = 0;  
    REP(i, n) {  
        chmax(dp[i+1][0], max(dp[i][0], dp[i][1]));  
        chmax(dp[i+1][1], max(dp[i][0], dp[i][1]));  
        if(s[i]=='0') chmax(dp[i+1][0], dp[i][0]+1);  
        if(s[i]=='9') chmax(dp[i+1][1], dp[i][1]+1);  
    }  
    cout << max(dp[n][0], dp[n][1]) << endl;  
  
    return 0;  
}