社区讨论

一种WA的区间DP写法但不知道哪里错了

P1220关路灯参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo7q5qjr
此快照首次捕获于
2023/10/27 05:57
2 年前
此快照最后确认于
2023/10/27 05:57
2 年前
查看原帖
dp[i][j][0/1]dp[i][j][0/1] 表示关掉 i~j 的路灯,i~j 路灯的最小耗电。这样就需要一个配套的 t[i][j][0/1]t[i][j][0/1] 数组存取最小耗电方案需要的时间,才能在后面计算出新的灯泡的耗电量。
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 条回复,欢迎继续交流。

正在加载回复...