CSUOJ 1141——第四届河南省程序设计大赛
2024-09-07 08:57:52
题目的意思是给你一个机器人,初始的时候在某一个给定的路灯位置,机器人要把路边所有的路灯关掉,每个路灯都有一个距离和一个功率,求要把所有的路灯关掉最小的最终能耗是多少?
题目是一个很明显的区间DP。可以这样考虑,机器人关掉一个区间的路灯后,一定停留在该区间的最左端或者最右端,而且必须包括起点,显然。
这样我们就可以区间dp了。
对于每一个含有初始位置的区间[i,j],只有两种位置使其最终的位置为j,那就是i和j-1。这样就得到了状态转移了。
接下来还有一个问题,就是怎么计算能耗呢?这样想,对于每个状态,表示关闭该区间的所有的灯后根据其所停留的位置,所有路灯的最小能耗总和。
所以我们可以对于每个路灯,用一个数组表示前面n个路灯的功耗总和,这样就可以dp了。
上代码:(效率还挺高的)
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1010
using namespace std; int f[][maxn][maxn],w[maxn],d[maxn],n,k,tep,tep1,tep2; int main()
{
while (scanf("%d",&n)!=EOF)
{
scanf("%d",&k);
for (int i=; i<=n; i++) scanf("%d%d",&d[i],&w[i]),w[i]+=w[i-];
memset(f,0x3f,sizeof f);
f[][k][k]=f[][k][k]=;
for (int i=k; i>; i--)
for (int j=k; j<=n; j++)
{
if (i==j) continue;
tep=w[n]-w[j]+w[i];
tep1=tep*(d[i+]-d[i])+f[][i+][j];
tep2=tep*(d[j]-d[i])+f[][i+][j];
f[][i][j]=min(tep1,tep2);
tep=w[n]-w[j-]+w[i-];
tep1=tep*(d[j]-d[j-])+f[][i][j-];
tep2=tep*(d[j]-d[i])+f[][i][j-];
f[][i][j]=min(tep1,tep2);
}
printf("%d\n",min(f[][][n],f[][][n]));
}
return ;
}
最新文章
- Spring Boot整合Dubbo框架demo
- NSOperationQueue与GCD的使用原则和场景
- SQL Server如何删除多余tempDB文件
- 关于 iOS 的一些学习资料
- Oracle自增列
- iOS网络请求之---GET和POST
- java class生成jar包(转)
- (转载)CSS中zoom:1的作用
- 9个Console控制台命令(转载)
- yii框架后台过滤器的使用 安全防护
- The Moving Points hdu4717
- mysql实现主从备份
- SQL对某个字段进行排名
- Java线程安全与锁优化
- 【转】简明 Vim 练级攻略
- mpvue小程序图片404
- 软件工程之四则运算--Github
- git 查看一个分支是否被合并过
- centos安装python与jdk
- java一些对象概念扫盲帖(DO VO DTO PO)