CF706C Hard problem DP

问题描述

CF706C

LG-CF706C

题解

显然是个线性DP。

设 \(f(i,0)\) 代表前 \(i\) 个字符串，且在第 \(i\) 个字符串不翻转的情况下，能够达成字典序的最小代价.

设 \(f(i,1)\) 代表前 \(i\) 个字符串，且在第 \(i\) 个字符串翻转的情况下，能够达成字典序的最小代价。

\(s,t\) 为字符串，若 \(s\) 的字典序比 \(t\) 小，记为 \(s<t\)

\(f(i,k)=min\{f(i,k),f(i-1,p)\}\) ，条件为 \(S(i-1,p)<S(i,k)\) 。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh=1;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    x*=fh;
}

const int INF=0x3f3f3f3f3f3f3f3fLL;
const int maxn=100007;

int n;
int c[maxn],opt[maxn][2];
string s[maxn],revs[maxn];

void Init(void){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++){
        cin>>s[i];
        revs[i]=s[i];
        for(int x=0,y=s[i].size()-1;x<=y;x++,y--) swap(revs[i][x],revs[i][y]);
    }
}

void Work(void){
//  memset(opt,INF,sizeof(opt));
//  for(int i=1;i<=n;i++) cout<<s[i]<<" "<<revs[i]<<endl;
    for(int i=1;i<=n;i++){
        opt[i][0]=opt[i][1]=INF;
        if(s[i]>=s[i-1]) opt[i][0]=min(opt[i][0],opt[i-1][0]);
        if(s[i]>=revs[i-1]) opt[i][0]=min(opt[i][0],opt[i-1][1]);
        if(revs[i]>=s[i-1]) opt[i][1]=min(opt[i][1],opt[i-1][0]+c[i]);
        if(revs[i]>=revs[i-1]) opt[i][1]=min(opt[i][1],opt[i-1][1]+c[i]);
    }
    int ans=min(opt[n][0],opt[n][1]);
    if(ans==INF) cout<<-1<<'\n';
    else cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    Init();
    Work();
    return 0;
}

CF706C Hard problem DP

原文：https://www.cnblogs.com/liubainian/p/12269471.html