[牛客月赛][初级][49]-E题 禅 线性DP题解

题目

 

样例输入 

2
5
1 2 3 4 0
5
4 4 4 4 0

样例输出 

2
5

题意理解

公主位置为0，走到公主身边要初始值最小是多少，可以任意选择起点。

比如第一个样例我从1这个位置走要严格大于这个位置的能力值。而这个能力值是1

那么我初始能力就要是2才能吃掉1，然后走过去就是3，然后吃掉2位置上的2，能力值就是5，以此类推我可以滚雪球吃掉位置3上的3，位置4上的4，然后到公主身边。

那么我们就可以想一想怎么递推过来，我们用dp[i]定义以i为起点我们走到公主身边初始能量值到底要多少。

那么状态转移方程就是

从右端出发：dp[i]=max(a[i]+1,dp[i-1]-a[i]);

从左端出发：dp[i]=max(a[i]+1,dp[i+1]-a[i]);

当然了起点的能力要严格大于当前格子能力 即dp[i]>=a[i]+1;

那么我们固定起点能力值 dp[i]=a[i]+1;

而且公主左右两侧 即pos-1和pos+1的初始能力值都是要固定好的

不是起点时

如果我们是从公主右边走到公主的位置上面

我们要在当前位置i与左边格子i-1减去当前格子的能力值

取一个max

我们在当前位置i的能力值是 起码严格大于a[i]的

而左边i-1的位置上 我们已经从右边走过去了 说明已经叠加了a[i]

那么我们就要看这个位置

是左边那个能力值减去a[i]剩下的多

还是我当前位置要花的能量多

那么从左边走过来也是同理分析

代码 

#include 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL ;
typedef pair PII;
typedef pair PDD;
#define fx first
#define fy second
const int INF=0x3f3f3f3f;
const LL  LINF=1e18;
const int N=1e5+10;
const int M=2e2+10;
const int MOD=1e9+7;
int n;
LL a[N],dp[N];
//dp[i] 以i为起点走到公主身边的最小能力值
void solve(){
	 scanf("%d",&n);
	 int pos=0;
	 for(int i=1;i<=n;i++){
	     dp[i]=0;
	 }
	 for(int i=1;i<=n;i++){
	 	scanf("%lld",&a[i]);
	 	if(!a[i])pos=i;//公主位置
	 }
	 if(n==1){
	 	puts("No Solution");
	 	return;
	 }
	 //从右边走到公主位置
	 for(int i=pos+1;i<=n;i++){
	     //起点的能力要严格大于当前格子能力 即dp[i]>=a[i]+1;
	     //那么我们固定起点能力值 dp[i]=a[i]+1;
	 	 dp[i]=a[i]+1;
	 	 if(i!=pos+1)dp[i]=max(dp[i],dp[i-1]-a[i]);
	 }
	 //从左边走到公主位置
	 for(int i=pos-1;i>=1;i--){
	     //起点的能力要严格大于当前格子能力 即dp[i]>=a[i]+1;
	     //那么我们固定起点能力值 dp[i]=a[i]+1;
	 	 dp[i]=a[i]+1;
	 	 if(i!=pos-1)dp[i]=max(dp[i],dp[i+1]-a[i]);
	 }
	 
	 LL res=LINF;
	 for(int i=1;i<=n;i++){
	 	if(i!=pos)res=min(res,dp[i]);
	 }
	 
	 printf("%lld\n",res);
	 return;
}

int main(){
    int T=1;
    scanf("%d",&T);
    while(T--){
    	solve();
	}
    
    return 0;
}