题意与分析
题意: 给出 \(n\) 个字符串, 可以反转任意串, 反转每个串都有其对应的花费 \(c_i\). 经过操作后是否能满足字符串 \(\forall i \in [1,n] \text{且} i \in R_+, str[i]\ge str[i-1]\), 若能输出最小花费, 否则输出 - 1.
分析: 经过各种字符串 dp 血虐, 应该会有个直觉:\(dp[i]\) 表示前 \(i\) 个串的最小花费. 但是好像不太够: 没有保存反转. 因此, 在 dp 中, 如果状态不够, 那就加维度保存状态. 这里就是: 我们定义 \(dp[i][0],dp[i][1]\) 分别保存最后一个的反转状态即可. 后面是很经典的套路了.
代码
- #include <bits/stdc++.h>
- using namespace std;
- vector<string> vec, vecr;
- array<long long,100005> cost;
- array<array<long long,2>, 100005> dp;
- int main()
- {
- iOS::sync_with_stdio(false);
- cin.tie(nullptr); cout.tie(nullptr);
- int n; cin>>n;
- for(int i=0;i!=n;++i)
- cin>>cost[i];
- for(int i=0;i!=n;++i)
- {
- dp[i][0]=dp[i][1]=1e15;
- string tmp; cin>>tmp;
- vec.emplace_back(tmp);
- reverse(tmp.begin(), tmp.end());
- vecr.emplace_back(tmp);
- }
- dp[0][0]=0; dp[0][1]=cost[0];
- int i;
- for(i=1;i!=n;++i)
- {
- if(vec[i]>=vec[i-1])
- dp[i][0]=dp[i-1][0];
- if(vecr[i]>=vec[i-1])
- dp[i][1]=dp[i-1][0]+cost[i];
- if(vec[i]>=vecr[i-1])
- dp[i][0]=min(dp[i][0], dp[i-1][1]);
- if(vecr[i]>=vecr[i-1])
- dp[i][1]=min(dp[i][1], dp[i-1][1]+cost[i]);
- if(dp[i][0]==1e15 && dp[i][1]==1e15) break;
- }
- if(i==n) cout<<min(dp[n-1][0], dp[n-1][1])<<endl;
- else cout<<-1<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2868268.html