首页 > 其他分享 >nyoj 304(区间dp)

nyoj 304(区间dp)

时间:2023-05-29 19:37:23浏览次数:43  
标签:min int 304 sum nyoj maxn dp dis


解题思路:这道题很明显是用区间dp,可是与以往的区间dp不同,因为对于区间[i,j],机器人所处的位置要么在i,要么在j(因为机器人要移动到某一点才能关闭灯泡,所以对于某一段区间来说,机器人最后肯定在两个端点上,否则将不能成立),那么既然要表示在左端点还是右端点,所以我们再开三维数组dp[i][j][0]表示停留在i点,dp[i][j][1]表示停留在j点,那么剩下的就是状态方程了,跟普通的区间dp一样,很容易写出来。。具体的看代码


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 1005;
int n,v,sum[maxn];
int dp[maxn][maxn][2],cost[maxn],dis[maxn];

void solve()
{
	memset(dp,0x1f,sizeof(dp));
	dp[v][v][0] = dp[v][v][1] = 0;
	for(int l = 2; l <= n; l++)
	{
		for(int i = 1; i <= n; i++)
		{
			int j = i + l - 1;
			if(j > n) break;
			dp[i][j][0] = min(dp[i][j][0],dp[i+1][j][0] + (sum[n]-sum[j]+sum[i])*(dis[i+1]-dis[i]));
			dp[i][j][0] = min(dp[i][j][0],dp[i+1][j][1] + (sum[n]-sum[j]+sum[i])*(dis[j]-dis[i]));
			dp[i][j][1] = min(dp[i][j][1],dp[i][j-1][0] + (sum[n]-sum[j-1]+sum[i-1])*(dis[j]-dis[i]));
			dp[i][j][1] = min(dp[i][j][1],dp[i][j-1][1] + (sum[n]-sum[j-1]+sum[i-1])*(dis[j]-dis[j-1]));
		}
	}
	printf("%d\n",min(dp[1][n][0],dp[1][n][1]));
}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		scanf("%d",&v);
		for(int i = 1; i <= n; i++)
			scanf("%d%d",&dis[i],&cost[i]);
		sum[0] = 0;
		for(int i = 1; i <= n; i++)
			sum[i] = sum[i-1] + cost[i];
		solve();
	}
	return 0;
}




标签:min,int,304,sum,nyoj,maxn,dp,dis
From: https://blog.51cto.com/u_16143128/6373651

相关文章

  • poj 2346(DP)
    题意:n位数,满足前n/2个数字之和同后n/2个数字之和相同的数一共有多少个?解题思路:dp[i][j]表示前i个数的和为j时,有多少个;递推关系:dp[i][j]+=dp[i-1][k],k表示前i-1个数的和,由于每一位只能是0-9,所以有限制条件:9>=j - k>=0由于对称性,只需要枚举到n/2即可,剩下的就是简单的乘法......
  • nyoj 307(最短路变形)
    解题思路:这道题和上一道题一样,也是最短路的变形,我之前的想法是二分答案,然后再dp去判断是否可以满足要求,但发现这样子的话会存在问题:因为一条路可能走多次,就无法保证其后效性。看了别人的思路:先以每个有宝藏的地方为起点,找到其到1号节点所符合题意的最大边max,表示最多可以从该节点运......
  • hdu 1511(dp)
    解题思路:两次dp确实很巧妙,我只想到了一次dp算出最后那个数最小,其实题目要求还要保证第一个数尽可能大,一开始也没有注意到。。AC:#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<math.h>#include<stdlib.h>#include<time.h>usingnamesp......
  • hdu 5086(dp)
    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5086题目大意:给出长度为n的数组,然后要求累计里面的每个子串的和。解题思路:这道题直接枚举肯定不行,所以要找递推关系。假设:{1,2,3,4}为某一个序列,假设我们已经找到了{1,2,3},接下来把{4}加入进去;由于{1,2,3}已经有{1},{2},{3},{1,......
  • 【Oracle impdp/expdp】Big lesson from failure with impdp/expdp in 12c
     最近忙于做数据库12c-19c迁移,基于公司的情况,选用了最拿手的expdp/impdporacle自带的王者级别工具进行迁移。按照常规思路,一顿操作猛如虎,expdp直接选用full=y将数据全库导出,然后在19c中导入,无论是12c中的导出还是19c中的导入数据,没有任何的错误,然而在无意间,反过来去检查下两......
  • upc 6888: 守卫(区间dp O(n^2) )
    6888:守卫时间限制:1Sec  内存限制:512MB提交:102  解决:33[提交][状态][讨论版][命题人:admin]题目描述九条可怜是一个热爱运动的女孩子。这一天她去爬山,她的父亲为了她的安全,雇了一些保镖,让他们固定地呆在在山的某些位置,来实时监视九条可怜,从而保护她。具体来......
  • upc 6597: Don't Be a Subsequence (字符串的最短不匹配子序列 dp)
    6597:Don'tBeaSubsequence时间限制:1Sec  内存限制:128MB提交:237  解决:45[提交][状态][讨论版][命题人:admin] 题目描述AsubsequenceofastringSisastringthatcanbeobtainedbydeletingzeroormorecharactersfromSwithoutchangingtheor......
  • wordpress 友情链接
    add_filter('pre_option_link_manager_enabled','__return_true'); 在你用的那个主题的function.php里面添加下面这个东东,然后去后台就多了一个链接,你添加就行了啊    前台怎么调用呢?看的别人的,也可以添加图片,就是不能上传,只能添加图片地址,主要的表就是wp_links......
  • Unity的IPostGenerateGradleAndroidProject:深入解析与实用案例
    UnityIPostGenerateGradleAndroidProjectUnity是一款流行的跨平台游戏引擎,它支持多种平台,包括Android。在Unity中,我们可以使用IPostGenerateGradleAndroidProject接口来自定义Gradle构建过程。本文将介绍如何使用IPostGenerateGradleAndroidProject接口,并提供三个使用例子。IPos......
  • 从注册表中删除RDP连接缓存
    打开注册表计算机\HKEY_CURRENT_USER\SOFTWARE\Microsoft\TerminalServerClient\Default根据需要删除如下键值:重启生效......