首页 > 其他分享 >HDU 5492 Find a path(DP)

HDU 5492 Find a path(DP)

时间:2023-06-12 14:31:56浏览次数:47  
标签:HDU min int s2 33 path inf Find dp


思路:将式子化开其实就是求(n+m-1)*s1-s2的最小值,s1表示各个格子的平方和,s2表示和的平方,留意到数据范围较小,令dp[i][j][k]为走到第i行第j列当前和为k的平方和的最小值,最后答案就是(n+m-1)*dp[i][j][k]-k*k



#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
int a[33][33];
int dp[33][33][1807];
int main()
{
    int T,cas=1;
	scanf("%d",&T);
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i = 1;i<=n;i++)
			for(int j = 1;j<=m;j++)
				scanf("%d",&a[i][j]);
		for(int i = 1;i<=n;i++)
			for(int j = 1;j<=m;j++)
				for(int k = 0;k<=1800;k++)
				  dp[i][j][k]=inf;
		for(int i = 1;i<=n;i++)
			for(int j = 1;j<=m;j++)
			{
				for(int k = 0;k<=1800;k++)
				{
                    if(i==1 && j==1 && a[i][j]==k)
						dp[i][j][k]=a[i][j]*a[i][j];
					if(k>=a[i][j])
					{
                        if(i>1)
							dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k-a[i][j]]+a[i][j]*a[i][j]);
						if(j>1)
							dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k-a[i][j]]+a[i][j]*a[i][j]);
					}
				}
			}
		int ans = inf;
		for(int i = 0;i<=1800;i++)
			if(dp[n][m][i]!=inf)
			ans = min(ans,(n+m-1)*dp[n][m][i]-i*i);
		printf("Case #%d: %d\n",cas++,ans);
	}
}


HDU 5492 Find a path(DP)_#define

标签:HDU,min,int,s2,33,path,inf,Find,dp
From: https://blog.51cto.com/u_16156555/6462563

相关文章

  • python学习笔记35-脚本有多个文件时如何指定import_path
    如果脚本涉及多个文件,且分布在多个目录中,则会涉及到import其它目录的文件.如果脚本不在脚本所在的目录run,则会涉及到run目录与脚本目录不相关.如何解决这个问题呢?假设目录结构如下:/a/b/c/bin/dfx.py/a/b/c/atpg/atpg.py/a/b/c/atpg/atpg_sim.py/a/b/c/common/my_......
  • 使用Xpath编写爬虫代码
    Xpath选择器爬取房源信息实例获取网页html,未处理子网页信息。python3.6foriinrange(1,101):print('正在爬取第'+str(i)+'页')#爬取北京上海广州深圳的二手房信息city=['bj','sh','gz','sz']forcincity:......
  • XPath官方手册中文版
    字号:大中小XPATH指南实例1基本的XPath语法类似于在一个文件系统中定位文件,如果路径以斜线/开始,那么该路径就表示到一个元素的绝对路径实例2如果路径以双斜线//开头,则表示选择文档中所有满足双斜线//之后规则的元素(无论层级关系)实例3星......
  • axis2 maven报错Could not find artifact org.apache.axis2:axis2:jar:1.7.9
    Couldnotfindartifactorg.apache.axis2:axis2:jar:1.8.2inaliyunmaven(https://maven.aliyun.com/repository/public/)一开始以为是镜像的问题,但是换成中央仓库也没用https://repo.maven.apache.org/maven2/org/apache/axis2/axis2/1.7.9/实际上,这个目录里确实没有j......
  • papamelon 349. 城市帮派 Find them, Catch them(挑战程序设计竞赛)
    地址https://www.papamelon.com/problem/349一个城市里有两个帮派,另外有N个成员,成员从1∼N进行编号,每个成员来自于其中一个帮派。给定M个信息,每个信息有两种格式:Dab:a,b(1≤a,b≤N,a≠b)两个人不是一个帮派的Aab:判断a,b(1≤a,b≤N,a≠b)两个人是否为同一个帮派......
  • spring boot ResourceUtil工具类获取不到jar的classPath下面文件问题
    先说结论这种方式是获取不到jar里面的文件的,但是在本地可以跑,打成jar包就读取不到文件了,即便ResourceUtils是spring提供的。Filefile=ResourceUtils.getFile("classpath:temp\\file\\info.txt");spring提供的ClassPathResource对象是可以在本地和jar环境都获取到资源......
  • HDU 5437 Alisha’s Party(优先队列模拟)
    思路:题目比较好懂的模拟题,用一个优先队列即可     模拟的时候要注意最后还会再开一次门,把剩下的人全部放进来,开门的时间并不一定是递增的,要自己排个序,还有就是要注意开门的时候是25这种数据,就是到第二个人到了开门,然后可以放5个人进来,这样不处理的话会RE#include<bits/s......
  • 设置_NT_SYMBOL_PATH(windbg)
    UsetheMicrosoftSymbolServertoobtaindebugsymbolfiles//z2011-09-0416:52:[email protected]转载请注明出处debugtoolsforwindows,windbg1.在windbg中可以使用如下命令:.sympathSRV*f:\localsymbols*http://msdl.microsoft.com/download/symbols设置_NT_SYMBOL_PAT......
  • ubuntu find whereis locate find
     which只能寻找执行文件,并在PATH变量里面寻找。whereis从linux文件数据库(/var/lib/slocate/slocate.db)寻找,所以有可能找到刚刚删除,或者没有发现新建的文件。locate同上,不过文件名是部分匹配。find是直接在硬盘上搜寻,功能强大,但耗硬盘,一般不要用。......
  • document.evaluate的详细用法(Xpath获取节点)
    document.evaluate的详细用法2006-12-2818:03使用 Greasemonkey 时会遇到的功能最为强大的一个工具就是 evaluate 函数。通过使用XPath这种查询语言,它可以用来寻找页面中的元素,属性和文本。 举个例子来说,如果您想获得某个页面上的全部链接。您也许会想到使用document.getEle......