社区讨论
一种WA的区间DP写法但不知道哪里错了
P1220关路灯参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo7q5qjr
- 此快照首次捕获于
- 2023/10/27 05:57 2 年前
- 此快照最后确认于
- 2023/10/27 05:57 2 年前
表示关掉 i~j 的路灯,i~j 路灯的最小耗电。这样就需要一个配套的 数组存取最小耗电方案需要的时间,才能在后面计算出新的灯泡的耗电量。
70分,错了 #6 7 10.
CPP#include <bits/stdc++.h>
using namespace std;
int n, c;
int p[55], ja[55];
int dp[55][55][2], t[55][55][2];
int main()
{
cin >> n >> c;
for (int i = 1; i <= n; i++)
cin >> p[i] >> ja[i];
memset(dp, 0x3f, sizeof dp);
memset(t, 0x3f, sizeof t);
t[c][c][0] = dp[c][c][0] = 0;
for (int len = 2; len <= n; len++) {
for (int i = 1, j=i+len-1; j <= n; i++, j++) {
if (dp[i+1][j][0] != 0x3f3f3f3f) {
t[i][j][0] = t[i+1][j][0]+(p[i+1]-p[i]);
dp[i][j][0] = dp[i+1][j][0]+t[i][j][0]*ja[i];
}
if (dp[i+1][j][1] != 0x3f3f3f3f) {
if (dp[i+1][j][1]+ja[i]*(t[i+1][j][1]+p[j]-p[i]) < dp[i][j][0]){
t[i][j][0] = t[i+1][j][1]+p[j]-p[i];
dp[i][j][0] = dp[i+1][j][1]+t[i][j][0]*ja[i];
}
}
if (dp[i][j-1][0] != 0x3f3f3f3f) {
t[i][j][1] = t[i][j-1][0]+(p[j]-p[i]);
dp[i][j][1] = dp[i][j-1][0]+t[i][j][1]*ja[j];
}
if (dp[i][j-1][1] != 0x3f3f3f3f) {
if (dp[i][j-1][1]+ja[j]*(t[i][j-1][1]+p[j]-p[j-1]) < dp[i][j][1]) {
t[i][j][1] = t[i][j-1][1]+p[j]-p[j-1];
dp[i][j][1] = dp[i][j-1][1]+t[i][j][1]*ja[j];
}
}
}
}
cout << min(dp[1][n][0], dp[1][n][1]) << endl;
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...