前提摘要

本次我負責的是2、6題

第二題

❀ 題目傳送門 ❀

❀ 解題小技巧 ❀

當啷，是無限背包，剛好是想講的主題。
無限背包，顧名思義就是四次元口袋可以拿一個東西無限次。
前面講過正常的背包，有提到「這邊有個細節：dp[限重] ~ dp[w[i]]而不是dp[w[i]] ~ dp[限重]」
因為轉移式為max(dp[j], dp[j-w[i]] + v[i])，也就是在更新dp[j]時，需藉著dp[j-w[i]]。
假設現在拿到第i個物品，分別討論兩種情形：

  • dp[限重] ~ dp[w[i]]（正常背包）：

    從大的找到小的
    令n是之後for跑的次數（因j--，跑n次為j-n），知道j > j-n所以j > (j-n)-w[i]，
    更新dp[j]時不可能動到dp[(j-n)-w[i]]，
    換言之dp[j]是0至i-1東西的最佳解，dp[j-w[i]] + v[i]是0至i東西的最佳解，
    也就是說背包不可能拿到重覆的東西。
    達成目的：一個東西最多拿一次。

  • dp[w[i]] ~ dp[限重]（無限背包）：

    從小的找到大的
    令n是之後for跑的次數（因j++，跑n次為j+n），而j < j+n所以(j+n)-w[i]可能大於、等於、小於j，
    更新dp[j]時有可能動到dp[(j+n)-w[i]]，
    這時dp[j]不一定是0至i-1東西的最佳解，dp[j-w[i]] + v[i]仍是0至i東西的最佳解，
    若dp[j]是0至i-1東西的最佳解，不會拿到重覆的東西。
    若dp[j]是0至i東西的最佳解，會拿到重覆的東西。
    也就是說背包有可能拿到重覆的東西。
    達成目的：一個東西可以拿無限次。

一樣舉個淺例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
原題目：
重量：１　２　３
價值：３　２　１
限重：３

初始化 dp 陣列，一開始每項都是 0
================================================
當 i = 0，可拿物：
重量：１
價值：３

當 i = 0，j = 1 時：
dp[1] = max(dp[1], dp[1-1(重量)] + 3)
=> dp[1] = max(dp[1], dp[0] + 3)
=> dp[1] = max(0, 0+3)
=> dp[1] = 3

當 i = 0，j = 2 時：
dp[2] = max(dp[2], dp[2-1(重量)] + 3)
=> dp[2] = max(dp[2], dp[1] + 3)
=> dp[2] = max(0, 3+3)
=> dp[2] = 6

當 i = 0，j = 3 時：
dp[3] = max(dp[3], dp[3-1(重量)] + 3)
=> dp[3] = max(dp[3], dp[2] + 3)
=> dp[3] = max(0, 6+3)
=> dp[3] = 9
================================================
當 i = 1，可拿物：
重量：１　２
價值：３　２

當 i = 1，j = 2 時：
dp[2] = max(dp[2], dp[2-2(重量)] + 2)
=> dp[2] = max(dp[2], dp[0] + 3)
=> dp[2] = max(6, 0+3)
=> dp[2] = 6

當 i = 1，j = 3 時：
dp[3] = max(dp[3], dp[3-2(重量)] + 2)
=> dp[3] = max(dp[3], dp[1] + 3)
=> dp[3] = max(9, 3+3)
=> dp[3] = 9
================================================
...略

從上述例子可發現，第一圈就拿了 3 次的物品1。

❀ 參考程式碼 ❀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define burst ios::sync_with_stdio(0); cin.tie(0);

int dp[100005];
int weight[1005], value[1005];

signed main(){
  burst
  memset(dp, 0, sizeof(dp));
  int n, w;
  cin >> n >> w;
  int ans = 0;
  for (int i = 0; i < n; i++){
    int a, b, c;
    cin >> a >> b >> c;
    value[i] = a;
    weight[i] = c;
    ans += a + b;
  }
  for (int i = 0; i < n; i++){
    for (int j = weight[i]; j <= w; j++){
      dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
      // cout << i << " " << j << " " << dp[j] << '\n';
    }
  }
  cout << dp[w] + ans;
  return 0;
}

第六題（非滿分解）

❀ 題目傳送門 ❀

❀ 解題小技巧 ❀

回文的題目，我之前剛好有摸過。因為一開始怕怕的就先用python解，才會有兩種解ㄏㄏ
處理單個字串 S 有幾個回文，分成兩類，其中|S|表示字串 S 的長度：

  • 第一類，奇數個字(像是aba、abcba)：

    將S[n]當作中心，放兩個指針，一個叫 left、一個叫 right
    left 會從n不斷往左跑、right 會從n不斷往右跑
    檢查S[left]跟S[right]是否相同

    • 若不相同或left < 0或right >= |S|，則將S[n+1]當作中心
    • 若相同且left >= 0且right < |S|，則多一個答案
  • 第二類，偶數個字(像是aa、abba)：

    將S[n]當作中心，放兩個指針，一個叫 left、一個叫 right
    left 會從n不斷往左跑、right 會從n+1不斷往右跑
    檢查S[left]跟S[right]是否相同

    • 若不相同或left < 0或right >= |S|，則將S[n+1]當作中心
    • 若相同且left >= 0且right < |S|，則多一個答案
      知道處理一個的方法後，只要切出自己要字串的就能解啦～

❀ 參考程式碼 ❀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
n = int(input())
s = input()
l = len(s)
s += s
ans = 0

for i in range(l):
    ans = 0
    string = s[i:i+n]
    # print(string)
    lenght = len(string)
    for i in range(lenght):
        left = i
        right = i
        while (left != -1 and right != -1) and (left != lenght and right != lenght) and string[left] == string[right]:
            ans += 1
            # print(ans, s[left:right+1])
            left -= 1
            right += 1
    for i in range(lenght-1):
        left = i
        right = i+1
        while (left != -1 and right != -1) and (left != lenght and right != lenght) and string[left] == string[right]:
            ans += 1
            # print(ans, s[left:right+1])
            left -= 1
            right += 1
    
    print(ans)
    # print("="*20)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define burst ios::sync_with_stdio(0); cin.tie(0);

signed main(){
  burst
  int n;
  string s;
  cin >> n >> s;
  int l = s.length();
  s += s;
  for(int i = 0; i < l; i++){
    int ans = 0;
    string str = s.substr(i,n);
    int len = str.length();
    for(int j = 0; j < len; j++){
      int left = j; 
      int right = j;
      while(left != -1 && right != -1 && left != len && right != len && str[left] == str[right]){
        ans += 1;
        left -= 1;
        right += 1;
      }
    }
    for(int j = 0; j < len-1; j++){
      int left = j; 
      int right = j+1;
      while(left != -1 && right != -1 && left != len && right != len && str[left] == str[right]){
        ans += 1;
        left -= 1;
        right += 1;
      }
    }
    cout << ans << "\n";
  }
  return 0;
}