发一道碰到的数组题

题目大概是这样的：
给你一个由'.'和'S'组成的长度为N的数组A，你可以最多做K次操作，每次操作选择一个数组中的位置，把相应位置连同左右邻居都变成'.'。
问K次操作之后，数组中最多可以有多少个'.'。
输入：
N K
A
输出
数组A中'.'的个数。

Constraint
1 <= N <= 1000
1 <= K <= 1000

然后我贴几个测试数据
格式：
N K
A
Answer

67 4
SS.S...S....SS..S..S.S.S...SS...SSS..SS.SS.SSSSS...S.S.S...S......S
48

29 2
.S.....SSSSS.SSSS...SS.SSS.SS
18

79 6
.S...SSS.SSS..SSSS.SSSSS.SS.S.SS.SS.SSSSSSS.SS...SS.S.SSS.SS.S.SS..S..S.SSS.SS.
47

743 69
S..S..S.S.S.SS..S...S..S.S.SS...SSS.S...S.S..S.S.SS.SSSSS.SS..SS.SS....SSS.S.S.S..SSS.....S.S.S.S.S..S.SSS..S.SSSSS...SSSSSS..S...S...S.SS.SS.....SS.......S.S.SSS.SSSSSS.S..S...SS.S...SS.SSSSSS.S.S..S..S..S.SS...SS..S..SS.SS.S..SS.S.SS..SSS.S.S.SSS..SS..SSS..S....S..S.S.SSSSSSSSSSSS..S.S.SSS....
563

458 83
..SSSSSS.SSS...SS.S.S..S...S.S..S.....SS.S.S..SSSSSS.SSSS..S.....S.....S.S...S...S....S...S....S.S.SSS....SSS....SSSS.S.........SSSS.S...SS..SS....S.SS..SS.SS.S..SS..SS..SS..SS..S.SS.SSSSSS.S.S....S..S...SS....SS........SS.S....S.S..S.SSSS.S..SSSSSSS.S..S....S.S.SS.SS.SSS.S.....S...S....S..SS...
431

401 72
SSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.S.SSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSS.SSSSSSSSSS.SSSS.SSSSSSS...
238

276 23
SSSSSS.SSS..SSS.SS.S.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSS.S.SSS.SSSSSS.SSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSSS.S.SSSS.SSSSSSSSSSSS.SSSSSSSSSSSSSSSS.SSS.S.SS.SSSSSSS.SSSSSSSS.SSS.S.
100

480 75
SSSS.SSSSSSSSSS.S.SS.SSSSSSSSSSS.SSS.SSSSSSS.SSSS.SSSSSS.SSS.SSSSSSSSSSSS.SSSS.S.SSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSS.SSSSS.SSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSS..SSSSSS.SS.SSSSSSSSSSSS.SSSSSSS.SSSSSSSSSSSS.SSSSSSSSS...
276

试了几个用模板扫的想法总是被一些case卡到，想想了也不知道怎么dp。dfs可以做但是O(2^N)的。


补充内容 (2019-6-17 14:05):
别的大数据有问题，请使用前3个和倒数第2个。抱歉。

补充内容 (2019-6-18 09:29):
再补充一个数据
6 2
S.SSSS
6

分享我的一个复杂度是O(NK)的贪心法。用链表管理数组A，每次贪心地从左到右看是否有连续三个S。如果有则都变成.，然后在链表里删除这三个S；如果没有则看是否连续三个里有两个S，有则都变成.，然后在链表里删除这三个字符；以此类推。这样重复K次。

这是我的证明（不一定对？）
先证明一个引理，第一次选中的三个字符一定出现在K次答案的最优解中。反证，如若不然，则任意一个最优解中都不包含这三个字符：
1. 最优解和这三个字符完全没有重叠：把最优解随便一次变换改成变换这三个字符，则解更优，否则与这三个字符是第一次最优的矛盾。
2. 最优解和这三个字符有一个位置重叠：把最优解包含了重叠字符的变换改成变换这三个字符，则解不比原先差，否则与这三个字符是第一次最优的矛盾。
3. 最优解和这三个字符有两个位置重叠：
3.1 重叠位置在最左或者最右：同理2得把包含重叠部分改成这三个字符不会更差。
3.2 重叠位置是左边一个右边一个：比如a b c d e f g，第一次选择了cde，但最优解包含abc和efg。
现在讨论abc中S的数量，显然abc中S的数量不能多于cde，否则与cde是第一次最优的矛盾。
3.2.1 abc中S的数量等于def中S的数量： 则我们的贪心法由于是从左到右的(关键)，会选择abc而不是cde，矛盾；（这里为了排除a-g是S.S.S.S的情况）
3.2.2 abc中S的数量少于def中S的数量：所以abc中S的数量少于等于bcd中S的数量，将abc改成bcd，不会使解更差。

这样就证明了，任意一个最优解，都是包含第一次我们选择的三个字符的，这样我们在链表里删掉这三个字符，就把问题的规模变成了N-3,K-1的一样问题，因此复杂度是O(NK)
我用这个算法试了67 29 79 276这4个case都是没问题的（别的好像数据有点问题）
如果有帮助还请加点大米~ 现在有好多东西都看不到呀

补充内容 (2019-6-15 22:02):
3.2.1 和3.2.2中 应该都是abc中S的数量等于（少于）cde（不是def）中S的数量，笔误~

1. public class Main {
   
2.     public static void main(String[] args) {
   
3.         InputStream inputStream = System.in;
   
4.         OutputStream outputStream = System.out;
   
5.         Scanner in = new Scanner(inputStream);
   
6.         PrintWriter out = new PrintWriter(outputStream);
   
7.         Main solver = new Main();
   
8.         solver.solve(1, in, out);
   
9.         out.close();
   
10.     }
    
11. 
    
12.     static class Main {
    
13.         public void solve(int testNumber, Scanner in, PrintWriter out) {
    
14.             int n = in.nextInt();
    
15.             int k = in.nextInt();
    
16.             String s = in.next();
    
17.             int[] a = new int[n + 1];
    
18.             for (int i = 1; i <= n; i++) {
    
19.                 a[i] = s.charAt(i - 1) == '.' ? 1 : 0;
    
20.             }
    
21.             int[][] dp = new int[n + 1][k + 1];
    
22.             for (int i = 1; i <= n; i++) {
    
23.                 dp[i][0] = dp[i - 1][0] + a[i];
    
24.                 for (int j = 1; j <= k; j++) {
    
25.                     dp[i][j] = dp[i - 1][j] + a[i];
    
26.                     if (i >= 3) {
    
27.                         dp[i][j] = Math.max(dp[i][j], dp[i - 3][j - 1] + 3);
    
28.                     }
    
29.                 }
    
30.             }
    
31.             int res = 0;
    
32.             for (int j = 0; j <= k; j++) {
    
33.                 res = Math.max(res, dp[n][j]);
    
34.             }
    
35.             out.println(res);
    
36.         }
    
37. 
    
38.     }
    
39. }
    

复制代码

来贴代码了，昨天睡觉的时候优化到了O(n)，其实证明链表里每次断裂后不会产生新的连续3个S(或者1，2个s，如果当前在检查相应的长度)即可，每遍都从前往后扫一遍就可以啦。

1. #include <iostream>
   
2. #include <vector>
   
3. #include <string>
   
4. #include <iterator>
   
5. #include <algorithm>
   
6. #include <list>
   
7. using namespace std;
   
8. 
   
9. int solve(string s,int n,int k)
   
10. {
    
11.     list<int> l;
    
12.     int res = 0;
    
13.     for(auto i:s){
    
14.         if(i=='.') // . converts to 1 and S converts to 0
    
15.         {
    
16.             res++;
    
17.             l.push_back(0);
    
18.         }else
    
19.             l.push_back(1);
    
20.     }
    
21.     for(int curCheck = 3; curCheck>=1 && k>0; curCheck--)
    
22.     {
    
23.         if(l.size()<3)
    
24.             break;
    
25.         auto i=l.begin(), j=i;
    
26.         int windowSum = *(i++);
    
27.         windowSum += *(i++);
    
28.         while(i!=l.end())
    
29.         {
    
30.             windowSum += *(i++);
    
31.             if(windowSum == curCheck)
    
32.             {
    
33.                 res += curCheck;
    
34.                 k--;
    
35.                 if(k == 0)
    
36.                     break;
    
37.                 l.erase(j++);
    
38.                 l.erase(j++);
    
39.                 l.erase(j++);
    
40.                 windowSum =0;
    
41.                 if(i == l.end())
    
42.                     break;
    
43.                 windowSum += *(i++);
    
44.                 if(i == l.end())
    
45.                     break;
    
46.                 windowSum += *(i++);
    
47.                 continue;
    
48.             }
    
49.             windowSum -= *(j++);
    
50.         }
    
51.     }
    
52.    
    
53.     return res;
    
54. }
    
55. 
    
56. int main(int argc, const char * argv[]) {
    
57.     cout<<solve("SS.S...S....SS..S..S.S.S...SS...SSS..SS.SS.SSSSS...S.S.S...S......S",67,4)<<endl;
    
58.     cout<<solve(".S.....SSSSS.SSSS...SS.SSS.SS",29,2)<<endl;
    
59.     cout<<solve(".S...SSS.SSS..SSSS.SSSSS.SS.S.SS.SS.SSSSSSS.SS...SS.S.SSS.SS.S.SS..S..S.SSS.SS.",79,6)<<endl;
    
60.     cout<<solve("SSSSSS.SSS..SSS.SS.S.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSS.S.SSS.SSSSSS.SSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSSS.S.SSSS.SSSSSSSSSSSS.SSSSSSSSSSSSSSSS.SSS.S.SS.SSSSSSS.SSSSSSSS.SSS.S.",276,23)<<endl;
    
61.     return 0;
    
62. }

复制代码

用heap 可以优化到O(nlogk）
基本思路就是如果对于一个全为S开头的子串 "S......S"， 必然是先把从最左边（或最右边）开始把若干个S（<=3) 变为 . 有些位置可以把转化3个S， 有些位置只能转化1或2个S， 我们总共就只能做K 次操作。 所以就选top k 个位置。 太懒了，就先贴一个nlogn 的代码吧， 如果限制heap的size为K, 那么负责度就是 nlogk.

1. 
   
2. #include <iostream>
   
3. #include <queue>
   
4. #include <string>
   
5. 
   
6. int solve(string s, int k) {
   
7.     priority_queue<int> q;
   
8.     int idx = 0;
   
9.     int ret = 0;
   
10.     while(idx < s.size()) {
    
11.         if(s[idx] == '.') {
    
12.             ret++;
    
13.             idx++;
    
14.         }
    
15.         else {
    
16.             int len = 0;
    
17.             while(idx + len < s.size() && s[idx + len] == 'S' && len <= 2)
    
18.                 len++;
    
19.             q.push(len);
    
20.             idx += len;
    
21.         }
    
22.     }
    
23.     while(k != 0 && !q.empty()) {
    
24.         ret += q.top();
    
25.         q.pop();
    
26.         k--;
    
27.     }
    
28.     return ret;
    
29. };
    
30. 
    
31. string t = "SSSSSS.SSS..SSS.SS.S.SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS.SS.SSSSSSSSSSSSSSSSSSS.SSSSSS.SSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSSSSS.SSSSSSSSSSSSSS.S.SSS.SSSSSS.SSSSSSSSSSS.SSSSSSSSSSSSS.SSSSSSS.S.SSSS.SSSSSSSSSSSS.SSSSSSSSSSSSSSSS.SSS.S.SS.SSSSSSS.SSSSSSSS.SSS.S.";
    
32. int main() {
    
33.     cout << solve(t, 23) << endl;
    
34.     return 0;
    
35. }
    

复制代码

seeker丶 发表于 2019-6-15 21:57
分享我的一个复杂度是O(NK)的贪心法。用链表管理数组A，每次贪心地从左到右看是否有连续三个S。如果有则都 ...

感谢讨论，干货满满。
我需要再思考一下。
同学说可以用dp做，复杂度差不多也是O(NK)，没想到还可以用链表做，学习了。

Neroldy 发表于 2019/06/15 23:48:22


感谢讨论，干货满满。
我需要再思考一下。
同学说可以用dp做，复杂度差不多也是O(NK)，没想到还可以用链表做，学习了。

如果知道了dp的做法麻烦分享一下！

zjck1995 发表于 2019-6-16 23:15
[mw_shl_code=java,true]public class Main {
    public static void main(String[] args) {
        In ...

不过兄弟这个代码不对吧？

补充内容 (2019-6-17 13:57):
妹的，我智障了，几个大数据有点问题。还请忽略。

seeker丶 发表于 2019-6-16 10:22
如果知道了dp的做法麻烦分享一下！

我的锅，大数据你会发现字符串没有N那么长，复制的时候出了问题。
dp解法你看楼下兄弟的，比我同学的那个还简洁。

seeker丶 发表于 2019-6-15 21:57
分享我的一个复杂度是O(NK)的贪心法。用链表管理数组A，每次贪心地从左到右看是否有连续三个S。如果有则都 ...

别的case因为太长，复制的时候出了错，所以只有你测的4个case是争取的。抱歉。

楼主牛逼！！！

https://leetcode.com/problems/max-consecutive-ones-iii/

补充内容 (2019-6-18 00:45):
类似的想法, 找at most k 'S'. 但是你这里可以一下改1, 2, 3个S. 所以如果是[1 - 3]个S连一块算一个S. O[n]的解法了

补充内容 (2019-6-18 00:52):
看了看题似乎理解错了.. 只是单纯的找最多的点吗..? 容我测一下

补充内容 (2019-6-18 01:09):
https://paste.ubuntu.com/p/SDkjFnqM8S/
能过你说的前三个跟倒数第二个测试.. 这题是谁理解错了