P1220 关路灯 （区间dp）
2024-10-11 04:38:23
题目链接：传送门
题目大意：
总共有N盏灯，老张从点C（1 ≤ C ≤ N）开始关灯（关灯不需要等待时间，C点的灯直接关掉），与此同时灯开始烧电（已知功率Pi）。
老张每次可以往左走关最近的灯或者往右走关掉最近的灯，耗时等于距离。问最少的烧电量。
1 ≤ N ≤ 50。
思路：
状态：
f[i][j]表示在已经关掉i，i+1，…，j的灯时已经浪费的电量。
讨论发现如果要转移状态，还需要加一维表示老站当前的位置：
f[i][j][0]表示老张在位置i，f[i][j][1]表示老张在位置j；
初始状态：
f[C][C][0] = f[C][C][1] = 0；
老张一开始可以直接关掉C点的灯。
状态访问顺序：
更新f[i][j]的时候需要知道f[i+1][j]和f[i][j-1]的状态。
也就是说从C点开始向两边访问即可。
状态转移方程：
f[i][j][0] = max(f[i+1][j][0] + 从点i+1走到点i所花费的时间 * 还没关掉的灯的总功率，
f[i+1][j][1] + 从点j走到点i所花费的时间 * 还没关掉的灯的总功率)
f[i][j][1] = max(f[i][j-1][0] + 从点i走到点j所花费的时间 * 还没关掉的灯的总功率，
f[i][j-1][1] + 从点j-1走到点j所花费的时间 * 还没关掉的灯的总功率)
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
const int MAX_N = ;
const ll INF = 0x3f3f3f3f3f3f3f3f; int N, C;
int pos[MAX_N];
ll P[MAX_N], sum[MAX_N], f[MAX_N][MAX_N][];// 0 表示停在左端，1 表示停在右端 void dp()
{
for (int i = C; i >= ; i--) {
for (int j = C; j <= N; j++) {
if (i == C && j == C) {
f[i][j][] = f[i][j][] = ;
continue;
}
// (i+1, j) -> (i, j)
if (i+ <= C) {
if (f[i][j][] > f[i+][j][] + (pos[i+] - pos[i]) * (sum[N] - sum[j] + sum[i])) {
f[i][j][] = f[i+][j][] + (pos[i+] - pos[i]) * (sum[N] - sum[j] + sum[i]);
}
if (f[i][j][] > f[i+][j][] + (pos[j] - pos[i]) * (sum[N] - sum[j] + sum[i])) {
f[i][j][] = f[i+][j][] + (pos[j] - pos[i]) * (sum[N] - sum[j] + sum[i]);
}
}
// (i, j-1) -> (i, j)
if (j- >= C) {
if (f[i][j][] > f[i][j-][] + (pos[j] - pos[i]) * (sum[N] - sum[j-] + sum[i-])) {
f[i][j][] = f[i][j-][] + (pos[j] - pos[i]) * (sum[N] - sum[j-] + sum[i-]);
}
if (f[i][j][] > f[i][j-][] + (pos[j] - pos[j-]) * (sum[N] - sum[j-] + sum[i-])) {
f[i][j][] = f[i][j-][] + (pos[j] - pos[j-]) * (sum[N] - sum[j-] + sum[i-]);
}
}
}
}
cout << min(f[][N][], f[][N][]) << endl;
return;
} int main()
{
cin >> N >> C;
sum[] = ;
for (int i = ; i <= N; i++) {
scanf("%d%lld", pos+i, P+i);
sum[i] = sum[i-] + P[i];
}
for (int i = C; i >= ; i--) {
for (int j = C; j <= N; j++) {
f[i][j][] = f[i][j][] = INF;
}
}
dp();
return ;
}
/*
4 3
2 10000
3 10
4 100
5 200 4 3
2 10000
3 200
4 100
5 10
*/
最新文章
- mysql while,loop,repeat循环，符合条件跳出循环
- javascript实现简单多文件上传
- 非Animal呢？为何不写个万用类
- OAF_开发系列13_实现OAF通过Vector动态查询设置（案例）
- Guava库
- QT5下获取本机IP地址、计算机名、网络连接名、MAC地址、子网掩码、广播地址
- UITableViewHeaderFooterView的使用+自己主动布局
- 设计师给了px显着的单位，Android要设置多少开发商dip、dp、sp？
- 搭建Mantis 缺陷管理系统
- Lua与javascript的差异
- iOS学习——图片压缩到指定大小以内
- 分享超好用的截动图工具ScreenToGif
- Chinese Mahjong UVA - 11210 （DFS）
- Intent的作用和表现形式简单介绍
- springboot注入properties配置到javabean
- tomcat端口号被占用的问题
- angular浏览器滚动条滚动到指定element 触发事件
- 深入浅出HTTPS基本原理
- CPP_类默认函数：构造函数，拷贝构造函数，赋值函数和析构函数
- was not registered for synchronization because synchronization is not active