Try   HackMD

第五場比賽 題解

程式碼都很短，不要緊張

z041：

這題其實就是基本的練習題目，只是做了一些小小改動
一個是狀態轉移的時候需要用 min，因為是取最小值，同時一開始的初始化就改為初始成一個極大值(注意不要設太大造成加法 overflow)
第二個點是每個狀態轉移都需要前一個狀態可以被滿足才能執行，因為題目的要求是重量不多不少恰好滿足，但是因為本題剛好是取 min 所以剛好不用檢查，大家可以想一下

#include <bits/stdc++.h>
using namespace std;

long dp[50000+30];
long const mx = 0x2222222222222222;

int main() {
  long n;
  cin >> n;
  while(n--) {
    memset(dp, 0x22, sizeof(dp));
    dp[0] = 0;
    long e, f;
    cin >> e >> f;
    long size = f - e;
    long r;
    cin >> r;
    for (long i = 0; i < r; ++i) {
      long p, w;
      cin >> p >> w;
      for (int j = w; j <= 50000; ++j) {
        dp[j] = min(dp[j], dp[j-w]+p);
      }
    }
    if (dp[size] == mx) {
      cout << "impossible" << endl;
    }
    else {
      cout << dp[size] << endl;
    }
  }
}

z042：

最重要的部分是本題不能 Greedy，其中一個反例是 100 99，可以仔細思考下
因此，我們要用 dp。
建立二維的 dp 表int dp[n][m]，其中的元素 dp[i][j] 代表的是長寬為 i、j 的時候，最少可以分割成幾個正方形。
葉子因為題目的限制，只有可能直的切或橫的切，假設我們從 2cm 的地方切，那麼這個長方形就可以切為 dp[i][2] + dp[i][j-2] 個正方形。因為 n 只有 100 所以可以直接列舉所有切的可能，詳情請看 Code:

#include <bits/stdc++.h>
using namespace std;

int main() {
  int dp[200][200];
  int n, m, i, j, k;
  cin >> n >> m;
  dp[1][1] = 1;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= m; j++) {
      dp[i][j] = INT_MAX;
      if (i == j) {
        dp[i][j] = 1;
        continue;
      }
      for (k = 1; k < i; k++) {
        dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k][j]);
      }
      for (k = 1; k < j; k++) {
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j - k]);
      }
    }
  }
  cout << dp[n][m] << endl;

  return 0;
}

z043：

這個需要想到三角形只能由，三個一樣長或是兩長一短兩種組合方式。

從長度最短的開始往後做，紀錄不成三角形的可憐棒棒，這種可憐棒棒只能由『兩長一短』的方式敗部復活成三角形。

#include <bits/stdc++.h>
#define ll long long 
using namespace std;

int n;
ll ans, s;
vector< ll > a;

int main() {
  cin >> n;
  a.resize(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) {
    ll pls = 0;
    if(s > 0) pls += (min(s, (a[i]/2))), s -= pls, a[i] -= (2*pls);
    ans += (pls+(a[i]/3));
    s += (a[i]%3);
  }
  cout << ans << endl;
  return 0;
}

z044：

用

v0,v1,v2 表示杯子容量的上限：

int v[3];

隨便估，發現所有杯子水量的狀態，最多有

2003 種…
才怪，只需要紀錄
v0 和
v1 大小的杯子就能推出
v2 目前水量為多少

所以只用二維陣列，去紀錄狀態是否拜訪：

bool vis[maxd][maxd];

從狀態

u 轉移到
v (也就是某杯子 j[s] 倒到別的杯子 j[t])：

for(int s = 0; s < 3; s++)
  for(int t = 0; t < 3; t++) {
    int pour = min(u.j[s], v[t] - u.j[t]);

    node v = u;
    v.j[s] -= pour;
    v.j[t] += pour;
    v.total += pour;
  }

將所有狀態都遍歷過，找出

d 或
d′ 即可。
而對於所有可能的
d′，當拜訪到的時候：

void update_ans(node n) {
  for(int i = 0; i < 3; i++)
    ans[n.j[i]] = min(ans[n.j[i]], n.total);
}

要保證從起始狀態到一個狀態的用水量最少，就用 priority queue 做保證：

priority_queue<node> PQ;

以下完整解題程式碼：

#include<bits/stdc++.h>
using namespace std;

int const maxd = 210;
int const INF = 0x3f3f3f3f;

struct node {
  int j[3], total; // j := jug
  bool operator<(node const &rhs) const
    { return total > rhs.total; } // min heap
};

int v[3], d, ans[maxd];
bool vis[maxd][maxd];

void update_ans(node n) {
  for(int i = 0; i < 3; i++)
    ans[n.j[i]] = min(ans[n.j[i]], n.total);
}

int main()
{
  scanf("%d%d%d%d", &v[0], &v[1], &v[2], &d); // a, b, c volume

  memset(vis, false, sizeof vis);
  memset(ans, 0x3f, sizeof ans);
  ans[0] = 0;
  priority_queue<node> PQ;
  PQ.push({0, 0, v[2], 0}); //root

  while(!PQ.empty()) {
    node u = PQ.top(); PQ.pop();

    update_ans(u);
    if(ans[d] != INF) break;

    if(vis[u.j[0]][u.j[1]]) continue;
    vis[u.j[0]][u.j[1]] = true;

    for(int s = 0; s < 3; s++)
      for(int t = 0; t < 3; t++) {
        int pour = min(u.j[s], v[t] - u.j[t]);

        node v = u;
        v.j[s] -= pour;
        v.j[t] += pour;
        v.total += pour;

        if(vis[v.j[0]][v.j[1]]) continue;
        PQ.push(v);
      }
  }

  for(int _d = d; _d >= 0; _d--)
    if(ans[_d] != INF) {
      printf("%d %d\n", ans[_d], _d);
      break;
    }

  return 0;
}

z045：

本題不能直接 DP 最佳路徑並將經過點改為 0 再 DP 一次，一反例如下：

3 4
0 3 1 2
1 3 1 1
2 3 3 4

所以需要一次 DP 兩條路徑，最直接的辦法是四維陣列 dp[m][n][m][n]，設 dp[a][b][c][d] 中 a, b 為第一條路線所在座標，c, d 為第二條路線所在座標。
但是此方法會超出記憶體限制，因此需要壓縮維度，將任意一維利用迴圈來做處理。

以下 code 中 dp[t][i][j]，i, j 代表兩條線各自 y 座標，t 為座標點 ( x, y ) 的 x+y，則路線所在位置的 x 座標可以 t 減去 y 座標得到。
以下 code 皆為了方便處理邊界，因此座標是從 ( 1, 1 ) 到 ( m, n )。

#include <bits/stdc++.h>
using namespace std;

int m, n, dp[205][105][105], p[105][105];

int main (int argc,char *argv[]) {
  memset(dp, 0, sizeof(dp));
  memset(p, 0, sizeof(p));
  cin >> m >> n;
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      cin >> p[i][j];
  for (int k = 3; k < m + n; k++)
    for (int b = 2; b <= n && b <= k - 1; b++)
      for (int a = 1; a < b; a++)
        dp[k][a][b] = max(dp[k - 1][a][b], max(dp[k - 1][a - 1][b], max(dp[k - 1][a][b - 1], dp[k - 1][a - 1][b - 1]))) + p[k - a][a] + p[k - b][b];
  cout << dp[m + n - 1][n - 1][n] + p[1][1] + p[m][n] << '\n';
  return 0;
}

所有點的期待值皆無負數，因此最大期待值的路線來回必定不相交，除了起點與終點，因此 i >= j 的狀況就不用記錄了。

可壓進二維，設 dp[i][j]，i 代表第一條線 y 座標，j 代表第二條線 y 座標。

#include <bits/stdc++.h>
using namespace std;

int m, n, dp[105][105], p[105][105];

int main (int argc, char *argv[]) {
  memset(dp, 0, sizeof(dp));
  memset(p, 0, sizeof(p));
	
  cin >> m >> n;
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      cin >> p[i][j];

  for (int i = 1; i <= m; i++)
    for (int b = 2; b <= n; b++) {
      for (int a = 1; a < b; a++)
        dp[a][b] = max(dp[a][b] + p[i][a] + p[i][b], dp[a - 1][b] + p[i][a]);
      for (int a = 1; a < b - 1; a++)
        dp[a][b] = max(dp[a][b], dp[a][b - 1] + p[i][b]);
    }
		
  cout << dp[n-1][n] << '\n';
  return 0;
}
Last changed by 
 
Yuessiah
0
537
Published on HackMD