C题，读懂题后一眼秒
题意 n个字符串，你可以翻转任意一个字符串，有c[i]的代价。求最小代价，使得n个字符串按非严格字典序排列（可相同）。不可能则输出-1。
一开始先把总长度小于10万看成了每个串小于10万，想不到该怎么做。
读懂题后秒懂dp
然后。。。
本来不想写的，感觉就乱搞一下就行，然后还是写了。
char comp，reverse，然后讨论16种情况。。。不想写copy了，就用了内置函数。
写了3K
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define maxn 100005 5 #define inf 10000000000000005 6 using namespace std; 7 long long n,dp[maxn][2],x[maxn]; 8 char now[maxn],next[maxn],revnow[maxn],revnext[maxn]; 9 void rev(){ 10 int len=strlen(next);revnext[len]=0; 11 for(int i=0;i<len;i++) 12 revnext[len-1-i]=next[i]; 13 } 14 bool strcomp(char* a,char* b){ 15 int lena=strlen(a),lenb=strlen(b),len=min(lena,lenb); 16 for(int i=0;i<len;i++){ 17 if(a[i]<b[i])return 1; 18 if(a[i]>b[i]) return 0; 19 } 20 if(lena>lenb) return 0; 21 else return 1; 22 } 23 int main(){ 24 scanf("%I64d",&n); 25 for(int i=1;i<=n;i++){ 26 scanf("%I64d",&x[i]); 27 } 28 scanf("%s",now);strcpy(next,now);rev();strcpy(revnow,revnext); 29 dp[1][0]=0;dp[1][1]=x[1];int comp1,comp2,comp3,comp4; 30 for(int i=2;i<=n;i++) 31 { 32 scanf("%s",next);rev(); 33 comp1=strcomp(now,next); 34 comp2=strcomp(revnow,next); 35 comp3=strcomp(now,revnext); 36 comp4=strcomp(revnow,revnext); 37 if(dp[i-1][0]==inf) comp1=0,comp3=0; 38 if(dp[i-1][1]==inf) comp2=0,comp4=0; 39 if(comp1){ 40 if(comp2){ 41 if(comp3){ 42 if(comp4){ 43 dp[i][0]=min(dp[i-1][0],dp[i-1][1]); 44 dp[i][1]=min(dp[i-1][0],dp[i-1][1])+x[i]; 45 } 46 else{ 47 dp[i][0]=min(dp[i-1][0],dp[i-1][1]); 48 dp[i][1]=dp[i-1][0]+x[i]; 49 } 50 } 51 else{ 52 if(comp4){ 53 dp[i][0]=min(dp[i-1][0],dp[i-1][1]); 54 dp[i][1]=dp[i-1][1]+x[i]; 55 } 56 else{ 57 dp[i][0]=min(dp[i-1][0],dp[i-1][1]); 58 dp[i][1]=inf; 59 } 60 } 61 } 62 else{ 63 if(comp3){ 64 if(comp4){ 65 dp[i][0]=dp[i-1][0]; 66 dp[i][1]=min(dp[i-1][0],dp[i-1][1])+x[i]; 67 } 68 else{ 69 dp[i][0]=dp[i-1][0]; 70 dp[i][1]=dp[i-1][0]+x[i]; 71 } 72 } 73 else{ 74 if(comp4){ 75 dp[i][0]=dp[i-1][0]; 76 dp[i][1]=dp[i-1][1]+x[i]; 77 } 78 else{ 79 dp[i][0]=dp[i-1][0]; 80 dp[i][1]=inf; 81 } 82 } 83 } 84 } 85 else{ 86 if(comp2){ 87 if(comp3){ 88 if(comp4){ 89 dp[i][0]=dp[i-1][1]; 90 dp[i][1]=min(dp[i-1][0],dp[i-1][1])+x[i]; 91 } 92 else{ 93 dp[i][0]=dp[i-1][1]; 94 dp[i][1]=dp[i-1][0]+x[i]; 95 } 96 } 97 else{ 98 if(comp4){ 99 dp[i][0]=dp[i-1][1]; 100 dp[i][1]=dp[i-1][1]+x[i]; 101 } 102 else{ 103 dp[i][0]=dp[i-1][1]; 104 dp[i][1]=inf; 105 } 106 } 107 } 108 else{ 109 if(comp3){ 110 if(comp4){ 111 dp[i][0]=inf; 112 dp[i][1]=min(dp[i-1][0],dp[i-1][1])+x[i]; 113 } 114 else{ 115 dp[i][0]=inf; 116 dp[i][1]=dp[i-1][0]+x[i]; 117 } 118 } 119 else{ 120 if(comp4){ 121 dp[i][0]=inf; 122 dp[i][1]=dp[i-1][1]+x[i]; 123 } 124 else{ 125 dp[i][0]=inf; 126 dp[i][1]=inf; 127 } 128 } 129 } 130 } 131 strcpy(now,next);strcpy(revnow,revnext); 132 } 133 dp[n][0]=min(dp[n][0],dp[n][1]); 134 if(dp[n][0]==inf) printf("-1 "); 135 else printf("%I64d ",dp[n][0]); 136 return 0; 137 }
A了以后去翻了翻cf上大神的代码
1 #define N (1<<17) 2 #define LL long long 3 #define INFP (1LL<<60) 4 #include <bits/stdc++.h> 5 using namespace std; 6 LL dp[N][2]; 7 int n,c[N][2]; 8 string s[N][2]; 9 int main() 10 { 11 cin>>n; 12 for(int i=1;i<=n;i++) 13 scanf("%d",&c[i][1]); 14 for(int i=1;i<=n;i++) 15 cin>>s[i][0],s[i][1]=s[i][0],reverse(s[i][1].begin(),s[i][1].end()); 16 for(int i=1;i<=n;i++) 17 for(int j=0;j<2;j++) 18 { 19 dp[i][j]=INFP; 20 for(int k=0;k<2;k++) 21 if(s[i][j]>=s[i-1][k]) dp[i][j]=min(dp[i][j],dp[i-1][k]+c[i][j]); 22 } 23 LL res=min(dp[n][0],dp[n][1]); 24 cout<<(res>=INFP?-1:res)<<endl; 25 }
。。。我傻逼
