洛谷 P1622 释放囚犯

Myth丶恋晨 2023-05-21 13:50 7阅读 0赞

题目传送门：[https://www.luogu.com.cn/problem/P1622][https_www.luogu.com.cn_problem_P1622]

转换为石子的合并问题。

区间DP+四边形优化。

#include<iostream>
    #include<set>
    using namespace std;
    const int MAXQ = 105;                     
    const int INF = 0x7fffffff;
    
    int dp[MAXQ][MAXQ];                       //dp[i][j]表示：把第i堆到第j堆合并，需要的成本 
    int s[MAXQ][MAXQ];                        //s[i][j]表示：第i堆到第j堆，最好的分割点 
    int a[MAXQ];
    int num[MAXQ];
    int sum[MAXQ];
    
    int initData(int p,int q){
    	for(int i=1;i<=q;i++){
    		cin>>a[i];	                       //输入堆的分割点 
    	}                             
    	a[q+1] = p+1;
    	for(int i=1;i<=q+1;i++){     
    		num[i] = a[i] - a[i-1] - 1;        //第i堆的人数 
    		sum[i] = sum[i-1] + num[i];        //前i堆的人数（不包括被释放的罪犯） 
    	}
    	for(int i=1;i<=q+1;i++){
    		dp[i][i] = 0;                      //初始化dp数组 
    		s[i][i] = i;                       //初始化s数组 
    	}
    }
    
    int main(){
    	int p,q;                                
    	cin>>p>>q;
    	initData(p,q); 
    	//一共q+1堆 
    	for(int len=1;len<=q;len++){
    		for(int start = 1;start+len<=q+1;start++){
    			int end = start + len;	
    			dp[start][end] = INF;
    			for(int k = s[start][end-1];k<=s[start+1][end];k++){
    				if(dp[start][end] > dp[start][k] + dp[k+1][end] + sum[end] - sum[start-1] + len -1){
    					dp[start][end] = dp[start][k] + dp[k+1][end] + sum[end] - sum[start-1] + len -1;
    					s[start][end] = k;
    				}
    			}
    		}
    	}
    	cout<<dp[1][q+1]<<endl;
    	return 0;
    }

[https_www.luogu.com.cn_problem_P1622]: https://www.luogu.com.cn/problem/P1622

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷 P1622 释放囚犯

题目传送门：[https://www.luogu.com.cn/problem/P1622][https_www.luogu.com.cn_problem_P1622] 转换

Myth丶恋晨/ 2023年05月21日 13:50/ 0 赞/ 8 阅读

相关洛谷P1093--奖学金

P1093 \[NOIP2007 普及组\] 奖学金 -------------------- [原题题意][Link 1] ------------------

妖狐艹你老母/ 2022年10月31日 12:19/ 0 赞/ 284 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 349 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 344 阅读

相关洛谷P1540——机器翻译

题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。题目描述这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义

傷城~/ 2022年04月14日 06:55/ 0 赞/ 329 阅读

相关洛谷P1002题解

include<iostream> using namespace std; long long a[30][30]={0},n,m,my,m

我会带着你远行/ 2022年03月19日 04:16/ 0 赞/ 377 阅读

相关洛谷 P1113 杂务

洛谷 P1113 杂务 Description `John`的农场在给奶牛挤奶前有很多杂务要完成，每一项杂务都需要一定的时间来完成它。比如：他们要将奶牛集合起

灰太狼/ 2021年11月10日 02:26/ 0 赞/ 391 阅读

相关 P1622释放囚犯

这是一道绿题，是一道让人想用贪心但却是区间DP的题目，难倒了我这个蒟蒻。这个题其实仔细观察是类似于石子合并的！合并石子的代价便是肉的数量，求最小代价。所以我们设dp\[i\

逃离我推掉我的手/ 2021年10月29日 09:12/ 0 赞/ 180 阅读

相关洛谷 P4961

目录题目思路 Code 题目 [戳][Link 1] 为了小埋A了这道题。思路读入原来的矩阵，将不是雷的格子更新为数字（数字就是

左手的ㄟ右手/ 2021年10月26日 20:28/ 0 赞/ 468 阅读

相关洛谷 P1396 营救

　　　　　　　　　　　　　　　　　　　　[洛谷 P1396 营救][P1396] 题目描述 “咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查

怼烎@/ 2021年10月01日 00:04/ 0 赞/ 470 阅读