1 条题解

  • 0
    @ 2024-6-4 15:27:10

    吃菜的区间版本。

    我们用tpl,r,k,dpl,r,ktp_{l,r,k},dp_{l,r,k}表示分别该神龙/xjc决策的时候,神龙还有kk张抢吃券,未来的最大答案是多少。

    那么,对于该神龙决策的时候:

    神龙有两类决策: (1)吃左边的或者是吃右边的。 (2)不吃了,把主动权交给xjc。

    xjc只有一种决策: (1)吃左边或者吃右边,然后把主动权交还给神龙。

    做过前置题,此题就没什么细节的,具体看代码。 时间/空间复杂度O(n3)O(n^3),考虑到神龙的抢吃券最多积累到255255张,或者是xjc的决策可以直接不用dp数组来保存,1G1G刚好够用。

    #include<bits/stdc++.h>
    #define maxn 505
    #define ll long long
    using namespace std;
    ll dp[maxn][maxn][255],tp[maxn][maxn][255];
    ll n,a[maxn];
    ll DP(int l,int r,int k);
    ll TP(int l,int r,int k);
    
    int tot=0;
    ll TP(int l,int r,int k)
    {
    	tot++;
    	if (l>r) return 0;
    	if (k>=(r-l+1)) return 0;
    	ll tt=tp[l][r][k];
    	if (tt!=0) return tt-1;
    	ll ans=DP(l,r,k); //不选,继续把机会让给对方
    	if (k>=1) 
    	{
    		ans=min(ans,TP(l+1,r,k-1));
    		ans=min(ans,TP(l,r-1,k-1));
    	}
    	tp[l][r][k]=ans+1;
    	return ans;	
    }
    
    ll DP(int l,int r,int k)
    {
    	tot++;
    	if (l>r) {return 0;}
    	ll tt=dp[l][r][k];
    	if (tt!=0) return tt-1;
    	ll ans=max(TP(l,r-1,k+1)+a[r],TP(l+1,r,k+1)+a[l]);
    	dp[l][r][k]=ans+1;
    	return ans;
    }
    
    int main()
    {
    	cin>>n;
    	for (int i=1;i<=n;i++) cin>>a[i];
    	DP(1,n,0);
    	cout<<dp[1][n][0]-1<<endl;
    }
    
    • 1

    信息

    ID
    1420
    时间
    3000ms
    内存
    1024MiB
    难度
    9
    标签
    (无)
    递交数
    135
    已通过
    15
    上传者