P1880 [NOI1995] 石子合并 题解
区间DP。
首先将其复制一遍（因为是环）。
设 \(f[i][j]\) 表示将 \(i\) 到 \(j\) 段的石子合并需要的次数。
有
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int n;
int a[N];
int s[N];
int f[N][N];
int g[N][N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], a[i + n] = a[i];
for (int i = 1; i <= n * 2; i++) s[i] = s[i - 1] + a[i];
memset(f, 0x3f, sizeof(f));
memset(g, 0xcf, sizeof(g));
for (int len = 1; len <= n; len++) {
for (int i = 1; i + len - 1 <= n * 2; i++) {
int j = i + len - 1;
if (len == 1) {
f[i][j] = 0;
g[i][j] = 0;
}
else {
for (int k = i; k < j; k++) {
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
}
}
}
}
int ans1 = 0x3f3f3f3f, ans2 = 0xcfcfcfcf;
for (int i = 1; i <= n; i++) ans1 = min(ans1, f[i][i + n - 1]), ans2 = max(ans2, g[i][i + n - 1]);
cout << ans1 << '\n' << ans2 << '\n';
return 0;
}
P5020 [NOIP2018 提高组] 货币系统 题解
转化为完全背包即可。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25010, M = 110;
int n;
int f[N];
int a[M];
void solve() {
int maxx = 0;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], maxx = max(maxx, a[i]);
memset(f, 0, sizeof(f));
f[0] = 1;
int ans = 0;
for (int i = 1; i <= n; i++) {
int x = a[i];
for (int j = x; j <= maxx; j++) {
f[j] += f[j - x];
}
}
for (int i = 1; i <= n; i++) if (f[a[i]] > 1) ans++;
cout << n - ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}
P1941 [NOIP2014 提高组] 飞扬的小鸟 题解
我们先不管障碍物。
设 \(f[i][j]\) 表示来到点 \((i,j)\) 的最少点击屏幕数。
因为每秒要不上升 \(k\times x[i]\)，要么下降 \(y[i]\)。
所以有：
\[f[i][j] = min(f[i - 1][j + y[i]], f[i - 1][j - k \times x[i]]) \]这表示从上一秒转移过来，要不是从上一秒下降下来，那么上一秒就在 \(j + y[i]\)，
要不是从上一秒上升上来，那么上一秒就在 \(j - k\times x[i]\)。
会 \(TLE\)。
下面进行优化：
首先看上升：
\(f[i][j] = min(f[i - 1][j - x[i]] + 1, f[i - 1][j - 2 \times x[i]] + 2, f[i - 1][j - 3 \times x[i]] + 3, \dots)\)
\(f[i][j - x[i]] = min(f[i - 1][j - 2 \times x[i]] + 1, f[i - 1][j - 3 \times x[i]] + 2, f[i - 1][j - 4 \times x[i]] + 3, \dots)\)
发现规律得：
\(f[i][j] = min(f[i - 1][j - x[i]] + 1, f[i][j - x[i]] + 1)\)。
下降直接处理即可，两个要分开处理！
细节：
- 初始状态:
-
要统计超出高度 \(m\) 的一些点。
-
遇到障碍，把相应的 \(f\) 值设为 \(\infty\)。
-
\(M\) 一定要开到 \(2000\)，因为 \(j + y[i]\) 可能达到 \(2000\)。
代码;
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010, M = 2010;
struct Node {
int x, l, r;
}c[N];
int n, m, cnt;
int x[N], y[N];
int f[N][M];
int cur = 1;
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> cnt;
for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
for (int i = 1; i <= cnt; i++) cin >> c[i].x >> c[i].l >> c[i].r;
sort(c + 1, c + cnt + 1, [](const Node& a, const Node& b){ return a.x < b.x; });
memset(f, 0x3f, sizeof(f));
for (int i = 0; i <= m; i++) f[0][i] = 0;
for (int i = 1; i <= n; i++) {
for (int j = x[i]; j <= m + x[i]; j++) {
f[i][j] = min(f[i - 1][j - x[i]] + 1, f[i][j - x[i]] + 1);
}
for (int j = m + 1; j <= m + x[i]; j++) {
f[i][m] = min(f[i][m], f[i][j]);
}
for (int j = 1; j <= m - y[i]; j++) {
f[i][j] = min(f[i][j], f[i - 1][j + y[i]]);
}
if (c[cur].x == i) {
int l = c[cur].l, r = c[cur].r;
while (l >= 0) f[i][l] = 0x3f3f3f3f, l--;
while (r <= m) f[i][r] = 0x3f3f3f3f, r++;
int ans = 0x3f3f3f3f;
for (int j = 0; j <= m; j++) ans = min(ans, f[i][j]);
if (ans == 0x3f3f3f3f) {
cout << 0 << '\n' << cur - 1 << '\n';
exit(0);
}
cur++;
}
}
int ans = 0x3f3f3f3f;
for (int i = 0; i <= m; i++) ans = min(ans, f[n][i]);
cout << 1 << '\n' << ans << '\n';
return 0;
}
祝大家在WC-2023上玩的愉快。
标签：include,const,min,int,基础,cin,times,动态,规划 From： https://www.cnblogs.com/PlayWithCPP/p/17372694.html