第五場比賽 題解
=
>程式碼都很短，不要緊張
# [z041](https://judge.cp.ccns.io/problem/z041)：
這題其實就是基本的練習題目，只是做了一些小小改動
一個是狀態轉移的時候需要用 min，因為是取最小值，同時一開始的初始化就改為初始成一個極大值(注意不要設太大造成加法 overflow)
第二個點是每個狀態轉移都需要前一個狀態可以被滿足才能執行，因為題目的要求是重量不多不少恰好滿足，但是因為本題剛好是取 min 所以剛好不用檢查，大家可以想一下
```cpp
#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](https://judge.cp.ccns.io/problem/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:
```cpp
#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](https://judge.cp.ccns.io/problem/z043)：
這個需要想到三角形只能由，三個一樣長或是兩長一短兩種組合方式。
從長度最短的開始往後做，紀錄不成三角形的可憐棒棒，這種可憐棒棒只能由『兩長一短』的方式敗部復活成三角形。
```cpp
#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](https://judge.cp.ccns.io/problem/z044)：
用 $v_0, v_1, v_2$ 表示杯子容量的上限：
```cpp
int v[3];
```
隨便估，發現所有杯子水量的狀態，最多有 $200^3$ 種...
才怪，只需要紀錄 $v_0$ 和 $v_1$ 大小的杯子就能推出 $v_2$ 目前水量為多少
所以只用二維陣列，去紀錄狀態是否拜訪：
```cpp
bool vis[maxd][maxd];
```
從狀態 $u$ 轉移到 $v$ (也就是某杯子 `j[s]` 倒到別的杯子 `j[t]`)：
```cpp
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'$，當拜訪到的時候：
```cpp
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 做保證：
```cpp
priority_queue<node> PQ;
```
以下完整解題程式碼：
```cpp
#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](https://judge.cp.ccns.io/problem/z045)：
本題不能直接 DP 最佳路徑並將經過點改為 0 再 DP 一次，一反例如下：
```cpp
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 )。
```cpp
#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 座標。
```cpp
#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;
}
```
Sign in with Wallet
Connect another wallet