首页 > 代码库 > codeforces 706C Hard problem DP(动态规划)问题

codeforces 706C Hard problem DP(动态规划)问题

题目链接http://codeforces.com/problemset/problem/706/C

题目大意:  给定n个字符串, 每个字符串可以颠倒前后位置(第一个字母到最后一个,第二个字母到倒数第二位) 每次颠倒需要花费ci的力气, 要求将所给的n个字符串用最小力气按字典序排列, 输出力气值, 如果无法按字典序排列, 则输出-1

数据范围:2?≤?n?≤?100?000 、 ci (0?≤?ci?≤?1e9) 所有字符串总长度不会超过1000000。

解题思路: 这是一道DP题, dp[i][0/1]分别表示第i个字符串不动或者颠倒, 做DP题的时候一定要时时刻刻记住学长说的那句话 DP很智能,想多了就把自己绕进去了。

当时自己没做出来 去百度了一下, 学到了直接用字符串, 还有用 reverse(b[i].begin(),b[i].end()); 可以直接将区间内倒序。 

这道题有几个坑点: 一 dp数组要开long long  、二 平时经常用const int MaxN = 1<<30 ; 做这道题想都没想就写上去了 结果wrong了一发, 后来才发现开一个long long类型的来比较  一般开到1e15比较保险;其他的都是普通dp套路。

代码如下:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<iostream>
 7 using namespace std;
 8 typedef long long LL;
 9 const int MaxN = 1e5;
10 const LL inf = 1e15;
11 int n;
12 LL num[MaxN + 5];
13 LL dp[MaxN + 5][2];
14 string a[MaxN + 5], b[MaxN + 5];
15 int len;
16 int main()
17 {
18     scanf("%d", &n);
19     for(int i = 1; i <= n; i++)
20         scanf("%I64d", &num[i]);
21     for(int i = 1; i <= n; i++){
22         cin >> a[i];
23         b[i]=a[i];
24         reverse(b[i].begin(),b[i].end());
25     }
26     for(int i = 1; i <= n; i++)
27         dp[i][0] = dp[i][1] = inf;
28     dp[1][0] = 0;
29     dp[1][1] = num[1];
30     int i;
31     for(i = 2; i <= n; i++){
32         if(a[i] >= a[i - 1])
33             dp[i][0] = dp[i - 1][0];
34         if(b[i] >= a[i - 1])
35             dp[i][1] = dp[i - 1][0] + num[i];
36         if(a[i] >= b[i - 1])
37             dp[i][0] = min(dp[i][0], dp[i - 1][1]);
38         if(b[i] >= b[i - 1])
39             dp[i][1] = min(dp[i][1], dp[i - 1][1] + num[i]);
40         if(dp[i][0] == inf && dp[i][1] == inf)
41             break;
42     }
43     if(i == n + 1)
44         printf("%I64d\n", min(dp[n][1], dp[n][0]));
45     else
46         printf("-1\n");
47     return 0;
48 }

 

codeforces 706C Hard problem DP(动态规划)问题