Codeforces Round #367 (Div. 2) C. Hard problem

题目链接:Codeforces Round #367 (Div. 2) C. Hard problem

题意:

给你一些字符串,字符串可以倒置,如果要倒置,就会消耗vi的能量,问你花最少的能量将这些字符串排成字典序

题解:

当时1点过头太晕了,看错题了,然后感觉全世界都会,就我不会,- -!结果就是一个简单的DP,

设dp[i][0]表示第i个字符串不反转的情况,dp[i][1]表示第i个字符串反转的情况

状态转移方程看代码

 #include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll; const int N=1e5+;
ll dp[N][],inf=(1ll<<)-;
int n,v[N],lena,lenb;
char a[N],b[N],c[N],d[N]; inline void up(ll &a,ll b){if(a>b)a=b;} int main()
{
scanf("%d",&n);
F(i,,n)scanf("%d",v+i);
scanf("%s",a),lena=strlen(a);
for(int i=,j=lena-;i<lena;i++,j--)c[j]=a[i];
dp[][]=,dp[][]=v[],c[lena]='\0';
F(i,,n)
{
scanf("%s",b),lenb=strlen(b),d[lenb]='\0';
for(int ii=,j=lenb-;ii<lenb;ii++,j--)d[j]=b[ii];
dp[i][]=dp[i][]=inf;
if(strcmp(a,b)<=)up(dp[i][],dp[i-][]);
if(strcmp(c,b)<=)up(dp[i][],dp[i-][]);
if(strcmp(a,d)<=)up(dp[i][],dp[i-][]+v[i]);
if(strcmp(c,d)<=)up(dp[i][],dp[i-][]+v[i]);
strcpy(a,b),strcpy(c,d),lena=lenb;
}
ll ans=min(dp[n][],dp[n][]);
printf("%I64d\n",ans==inf?-:ans);
return ;
}
上一篇:Android Support v4、v7、v13的区别和应用场景


下一篇:80、Android Support v4、v7、v13的区别以及应用场景