P7958 [COCI2014-2015#6] NEO

2024-09-03 12:52
文章标签 2015 neo p7958 coci2014

本文主要是介绍P7958 [COCI2014-2015#6] NEO,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目大意

翻译的基本题面就不多说了,我们来大概分析一下题目。

  • 序列会变回来:我们可以观察到,在 n n n 次变换后,序列会还原。也就是说,两个循环在同一个 i i i 上操作的序列是一样的。
  • 下标的空间:然后我们再分析一下不难发现,下标是一大一小,也就是 min ⁡ ( I D i , I D i + 1 ) \min\left(ID_{i},ID_{i+1}\right) min(IDi,IDi+1) min ⁡ ( I D i , I D i + 1 ) + 1 \min\left(ID_{i},ID_{i+1}\right)+1 min(IDi,IDi+1)+1,所以我们求 I D i ID_i IDi 时,去求 I D i − 1 ID_{i-1} IDi1 就好了。聪明的小朋友想到动态规划了,那么再找找。
  • 连续性:再找一找就可以发现就是选择一些边,那么就可以知道状态之间是关联的。

思路概述

经过了上面的思考,我们就不难可以发现,这道题肯定用动态规划。我总结了两种方法供大家食用:

强行 dp

这种思路是我一开始想出来的,其实挺好设的。我们就设 f i , j f_{i,j} fi,j 表示在 i i i 的时候选 j j j 所能取到的最大贡献,所以我们就可以得到一个转移方程。
f i , j = max ⁡ k = 1 n − 1 ( f i − 1 , k + A min ⁡ ( j , k ) − A max ⁡ ( j , k ) + 1 ) f_{i,j}=\max_{k=1}^{n-1}\left(f_{i-1,k}+A_{\min\left(j,k\right)}-A_{\max\left(j,k\right)}+1\right) fi,j=k=1maxn1(fi1,k+Amin(j,k)Amax(j,k)+1)
但是肯定有同学一眼丁真,发现时间复杂度太大了,所以我们优化成这个样子:
f i , j = max ⁡ ( A j + max ⁡ k = j n − 1 ( f i − 1 , k − A k + 1 ) − A j + 1 + max ⁡ k = 1 j ( f i − 1 , k + A k ) ) f_{i,j}=\max\left(A_j+\max_{k=j}^{n-1}\left(f_{i-1,k}-A_{k+1}\right)-A_{j+1}+\max_{k=1}^{j}\left(f_{i-1,k}+A_{k}\right)\right) fi,j=max(Aj+k=jmaxn1(fi1,kAk+1)Aj+1+k=1maxj(fi1,k+Ak))
然后后面的东西我们可以使用前缀或者是后缀和搞定。然后我们上一下核心代码:

pre[0]=suf[n]=-1e9;
for(i=1;i<=n;++i,solve()){for(k=1;k<n;++k){if(pre[k-1]>=f[i-1][k]+A[k]){pre[k]=pre[k-1];pref[k]=pref[k-1];}else{pre[k]=f[i-1][k]+A[k];pref[k]=k;}}for(k=n-1;k;--k){if(suf[k+1]>=f[i-1][k]-A[k+1]){suf[k]=suf[k+1];suff[k]=suff[k+1];}else{suf[k]=f[i-1][k]-A[k+1];suff[k]=k;}}for(j=1;j<n;++j){int p=pre[j]-A[j+1],s=suf[j]+A[j];if(p>=s){f[i][j]=p;trans[i][j]=pref[j];}else{f[i][j]=s;trans[i][j]=suff[j];}}
}

但是,这个空间复杂度不够优秀,所以我们再换一种。

正解

那么我们可以对于每一个 i i i ,我们可以设
i d 1 = min ⁡ ( I D i , I D i + 1 ) , i d 2 = m i n ( I D i , I D i + 1 ) id_1=\min(ID_i,ID_{i+1}),id2=min(ID_i,ID_{i+1}) id1=min(IDi,IDi+1),id2=min(IDi,IDi+1)
所以,我们就可以得到 s u m = A i d i − A i d 2 + 1 sum=A_{id_i}-A_{id_2+1} sum=AidiAid2+1
同时,这也让我们想到了差分这件事情,所以我们可以构建出一个 ( n − 1 ) × n \left(n-1\right)\times n (n1)×n 的矩阵,每一行都是旋转后记录的差分数组。但是动态规划的数组怎么设计呢?其实很简单,设 f i , j , k f_{i,j,k} fi,j,k 表示走到了 ( i , j ) \left(i,j\right) (i,j) 这个位置的时候,方向是 k k k 的最长路径,所以就有如下的转移方程。
f i , j , 0 = max ⁡ ( f i − 1 , j , 0 / 1 / 2 + B i , j ) f i , j , 1 = max ⁡ ( f i , j + 1 , 0 / 1 + B i , j ) f i , j , 2 = max ⁡ ( f i , j − 1 , 0 / 2 + B i , j ) f_{i,j,0}=\max\left(f_{i-1,j,0/1/2}+B_{i,j}\right) f_{i,j,1}=\max\left(f_{i,j+1,0/1}+B_{i,j}\right) f_{i,j,2}=\max\left(f_{i,j-1,0/2}+B_{i,j}\right) fi,j,0=max(fi1,j,0/1/2+Bi,j)fi,j,1=max(fi,j+1,0/1+Bi,j)fi,j,2=max(fi,j1,0/2+Bi,j)
代码就不贴了。

这篇关于P7958 [COCI2014-2015#6] NEO的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1133008

相关文章

CF Bayan 2015 Contest Warm Up B.(dfs+暴力)

B. Strongly Connected City time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/probl

CF Bayan 2015 Contest Warm Up A.(模拟+预处理)

A. Bayan Bus time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/problem/A The fi

2015年校赛总结

题目名为“校赛总结”,其实更想换成“Rainbow为什么五题滚粗?!”。作为今年校赛大二没拆的两个队伍之一,结果打成这样,没脸见人了,总结起来就是我认为自己今天SB了。主要有以下几点: 1.我今天状态的确不好,最后卡的那道B题跟去年在农大校赛上遇见的那题类似,在最后那段时间我已经有思路了,可是由于当时不敢写。等到最后15分钟才开始敲,加上我用很麻烦的Dijstra那种方法,调试起来好多细节要处理

百度之星 2015 复赛 1001 (数长方形)

数长方形    Accepts: 595    Submissions: 1225  Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description 小度熊喜欢玩木棒。一天他在玩木棒的时候,发现一些木棒会形成长方形

百度之星 2015 初赛(1) 1002 找连续数

找连续数      Accepts: 401      Submissions: 1911  Time Limit: 2000/1000 MS (Java/Others)      Memory Limit: 32768/32768 K (Java/Others) Problem Description 小度熊拿到了一个无序的数组,对于这个数组,小度熊想知道是

2015多校联合训练第三场Work(hdu5326)

题意: a是b的上司,b是c的上司,则a是c的上司,问构成一个树种,有多人是 k个人的上司 思路: 先找出root,然后dfs一下就行 #include <bits/stdc++.h>#define LL long longusing namespace std;const int MAXN = 1e6;int f[105];int n, k;int mp[101][101];

2015年多校联合训练第三场RGCDQ(hdu5317)

题意: f(i)代表i数中有的素数的种数,给出区间[l,r],求区间内max(gcd(f(i))), 由于i最大是1e6,2*3*5*7*11*13*17>1e6,故最多不超过7种素数, 先打表打出1e6内的素数种数表,然后用sum[i][j]代表1-i个数中,还有j个素数的个数,最后用sum[r][j] - sum[l-1][j]求出区间内含有j个素数的数的个数,暴力找出1,2,3,4,5

2015多校联合训练第一场Tricks Device(hdu5294)

题意:给一个无向图,给起点s,终点t,求最少拆掉几条边使得s到不了t,最多拆几条边使得s能到t 思路: 先跑一边最短路,记录最短路中最短的边数,总边数-最短边数就是第二个答案 第一个答案就是在最短路里面求最小割,也就是求最大流,然后根据最短路在建个新图,权为1,跑一边网络流 模板题,以后就用这套模板了 #include <iostream>#include <cstdio>#incl

2015多校联合训练第一场Assignment(hdu5289)三种解法

题目大意:给出一个数列,问其中存在多少连续子序列,子序列的最大值-最小值< k 这题有三种解法: 1:单调队列,时间复杂度O(n) 2:RMQ+二分,时间复杂度O(nlogn) 3:RMQ+贪心,时间复杂度O(nlogn) 一:RMQ+二分 RMQ维护最大值,最小值,枚举左端点i,二分找出最远的符合的右端点j,答案就是ans += j - i+1;(手推一下就知道) 比如1 2 3

2015年多校联合训练第一场OO’s Sequence(hdu5288)

题意:给定一个长度为n的序列,规定f(l,r)是对于l,r范围内的某个数字a[i],都不能找到一个对应的j使得a[i]%a[j]=0,那么l,r内有多少个i,f(l,r)就是几。问所有f(l,r)的总和是多少。 公式中给出的区间,也就是所有存在的区间。 思路:直接枚举每一个数字,对于这个数字,如果这个数字是合法的i,那么向左能扩展的最大长度是多少,向右能扩展的最大长度是多少,那么i为合法的情况