Codeforces Round #560 (Div. 3)C. Good String

タイトルリンク:https://codeforces.com/contest/1165/problem/C
标题:単語文字列a[i]!=a[i+1] .
考え方:直接前から後まで遍歴して、貪欲でいいです.
参照コード:

#include
using namespace std;
#define LL long long
#define PII pair
#define PB push_back
#define POP pop_back
#define FI first
#define SE second
#define endl '
'
#define ls x<<1
#define rs x<<1|1
const int N=2e6+7,mod=1e9+7,INF=1e9;
const double pi = acos(-1.0);
string s;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        char a;
        cin >> a;
        if(s.size() % 2 == 0 || a != s.back())
            s.push_back(a);
    }
    if(s.size() % 2)
        s.pop_back();
    cout << n - s.size() << endl;
    cout << s << endl ;
    return 0;
}

添付:ToRe様のdpコード(tql)

#include 
using namespace std;
void debug() { cout << endl; }
template  void debug (T f, R ...r) { cout << "[" << f << "]"; debug (r...); }
template  T mmin(T a, T b) { return min(a,b); }
template  T mmin(T a, R... b) { return min(a,mmin(b...)); }
template  T mmax(T a, T b) { return max(a,b); }
template  T mmax(T a, R... b) { return max(a,mmax(b...)); }
template  T mgcd(T a, T b) { return __gcd(a,b); }
template  T mgcd(T a, R... b) { return __gcd(a,mgcd(b...)); }

void myin()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
}

namespace IO
{
const int MX = 4e7;
char buf[MX];
int c, sz;
void begin()
{
    c = 0;
    sz = fread(buf, 1, MX, stdin);
}
inline bool read(int &t)
{
    while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;
    if(c >= sz) return false;
    bool flag = 0;
    if(buf[c] == '-') flag = 1, c++;
    for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';
    if(flag) t = -t;
    return true;
}
}

#define ll long long
#define _p pair
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define fi first
#define se second

char s[200005];
int wtf[200005];
int dp[200005][30][2], path[200005][30][2], flag[200005][30][2];

int main()
{
    int n;
    scanf("%d%s",&n,s+1);
    for(int i = 1; i <= n; ++i) wtf[i] = s[i]-'a';

    memset(dp,0x3f,sizeof(dp));
    memset(path,-1,sizeof(path));
    flag[1][wtf[1]][1] = 1;
    dp[1][wtf[1]][1] = 0;
    for(int i = 0; i < 26; ++i) dp[1][i][0] = 1;

    for(int i = 2; i <= n; ++i)
    {
        int minn = 0x3f3f3f3f, id1, minfq = 0x3f3f3f3f, id2;
        for(int j = 0; j < 26; ++j) dp[i][j][0] = dp[i-1][j][0]+1, path[i][j][0] = j; // del
        for(int j = 0; j < 26; ++j) dp[i][j][1] = dp[i-1][j][1]+1, path[i][j][1] = j; // del

        for(int j = 0; j < 26; ++j)
        {
            if(dp[i-1][j][0] < minn)
            {
                minn = dp[i-1][j][0];
                id1 = j;
            }
        }
        for(int j = 0; j < 26; ++j)
        {
            if(j != wtf[i] && minfq > dp[i-1][j][1])
            {
                minfq = dp[i-1][j][1];
                id2 = j;
            }
        }
        if(dp[i][wtf[i]][1] > minn)
        {
            dp[i][wtf[i]][1] = minn;
            path[i][wtf[i]][1] = id1;
            flag[i][wtf[i]][1] = 1;
        }
        if(dp[i][wtf[i]][0] > minfq)
        {
            dp[i][wtf[i]][0] = minfq;
            path[i][wtf[i]][0] = id2;
            flag[i][wtf[i]][0] = 1;
        }
    }
    int ans = 0x3f3f3f3f, id, cur = 0, wzy = 0;
    for(int i = 0; i < 26; ++i)
    {
        if(dp[n][i][0] < ans)
        {
            ans = dp[n][i][0];
            id = i;
        }
    }
    stack fq;
    printf("%d
",ans);
    for(int i = n; i > 0; --i)
    {
        if(id == -1) break;
        if(flag[i][id][cur])
        {
            fq.push(id);
            wzy = 1;
        }
        id = path[i][id][cur];
        if(wzy) wzy = 0, cur ^= 1;
    }
    while(!fq.empty())
    {
        int tmp = fq.top();
        fq.pop();
        printf("%c",tmp+'a');
    }
    printf("
");
    return 0;
}