android开发实战 mfc acm configuration pip scripting flink教程视频 网盘源码 change事件 查看kafka消费情况 网络游戏server编程 当前时间减一天 mysql查询结果拼接 wordpress本地建站 python语言编程入门 python循环10次 python如何定义变量 java基础 java实战 java结构 linux中grep 两表关联查询 vbs表白代码 地球末日攻略 图片放大软件 winhex教程 16进制编辑器 python延时函数 bin文件编辑器 商标查询软件 idea下载 谷歌浏览器升级 机箱最佳风道图 su模型交错 小程序图片上传 任务栏跑到右侧怎么办 网红男头像 qq网盘在哪里 笔记本摄像头软件 武极加点
当前位置: 首页 > 学习教程  > 编程语言

acm-(dp)Codeforces Round #688 (Div. 2) F. Even Harder

2020/12/5 9:37:59 文章标签:

传送门 设dp[i][j](j≥i)dp[i][j](j\ge i)dp[i][j](j≥i)表示到达iii点只有一条路径且满足能够到达iii点的这个唯一的点kkk能到达的最远点最多是jjj。 于是不难写出方程dp[i][ja[j]]min{dp[i][ja[j]],dp[j][i−1]cnt[j][i−1]}dp[i][ja[j]]min\{dp[i][ja[j]],dp[j][i-1]cnt[j]…

题面
传送门
d p [ i ] [ j ] ( j ≥ i ) dp[i][j](j\ge i) dp[i][j](ji)表示到达 i i i点只有一条路径且满足能够到达 i i i点的这个唯一的点 k k k能到达的最远点最多 j j j

于是不难写出方程 d p [ i ] [ j + a [ j ] ] = m i n { d p [ i ] [ j + a [ j ] ] , d p [ j ] [ i − 1 ] + c n t [ j ] [ i − 1 ] } dp[i][j+a[j]]=min\{dp[i][j+a[j]],dp[j][i-1]+cnt[j][i-1]\} dp[i][j+a[j]]=min{dp[i][j+a[j]],dp[j][i1]+cnt[j][i1]},其中 j + a [ j ] ≥ i j+a[j]\ge i j+a[j]i c n t [ l ] [ r ] cnt[l][r] cnt[l][r]代表从 l l l r r r的点能够到达 i i i的数量,这些点也是必须要被清理的,并且这些点的数量很容易被维护。

int a[maxn],dp[maxn][maxn];

int main(){
	int t=rd();
	while(t--){
		int n=rd();
		FOR(i,1,n+1)a[i]=rd();
		FOR(i,2,n+1)dp[1][i]=0;
		FOR(i,2,n+1){
			int cnt=0;
			FOR(j,i,n+1)dp[i][j]=inf/2;
			ROF(j,i-1,1){
				if(j+a[j]>=i){
					dp[i][j+a[j]]=min(dp[i][j+a[j]],dp[j][i-1]+cnt);
					cnt++;
				}
			}
			FOR(j,i+1,n+1)dp[i][j]=min(dp[i][j],dp[i][j-1]);
		}
		wrn(dp[n][n]);
	}
}

本文链接: http://www.dtmao.cc/news_show_450037.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?