【区间DP】取数游戏

我就是我 2024-03-24 10:23 4阅读 0赞

**1A，我可真牛逼**

[1027-取数游戏2\_2021秋季算法入门班第七章习题：动态规划1 (nowcoder.com)][1027-_2_2021_1 _nowcoder.com]

题意：

![a236168cc63041acaf3e1a00a597f125.png][]

思路：

一眼区间DP

状态设计：dp\[l\]\[r\] 表示把区间\[l,r\]的数取完的最大价值

状态转移：

决策只有两种，头和尾，考虑这两种决策就行

然后取了多少数是已经确定的，就是：int t=n-(r-(l+1)+1);

边界搞不清楚就拿\[1,n\]套进去凑一凑就行了

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    const int mxn=1e3+10;
    const int mxe=1e6+10;
    int n;
    int a[mxn],b[mxn];
    int dp[mxn][mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        memset(dp,-0x3f,sizeof(dp));
        for(int len=1;len<=n;len++){
            for(int l=1;l+len-1<=n;l++){
                int r=l+len-1;
                if(len==1) dp[l][r]=a[l]*b[n];
                else{
                    int t=n-(r-(l+1)+1);
                    dp[l][r]=max(dp[l][r],max(dp[l+1][r]+b[t]*a[l],dp[l][r-1]+b[t]*a[r]));
                }
            }
        }
        cout<<dp[1][n]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[1027-_2_2021_1 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/24213/1027
[a236168cc63041acaf3e1a00a597f125.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4eea276592c243a8a3872962e19615ff.png

发表评论取消回复

表情：

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

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

相关阅读

相关【区间DP】Zuma

虽然是典中典，但是不妨碍我不会 [CF607B Zuma - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][CF607B Zuma - _ _ _ _luo

我不是女神ヾ/ 2024年03月26日 21:17/ 0 赞/ 37 阅读

相关【区间DP】取数游戏

1A，我可真牛逼 [1027-取数游戏2\_2021秋季算法入门班第七章习题：动态规划1 (nowcoder.com)][1027-_2_2021_1 _nowcoder.c

我就是我/ 2024年03月24日 10:23/ 0 赞/ 5 阅读

相关区间dp问题

区间dp一般有以下几种类型的题目：如何将环形区间问题转换为线性dp问题如何记录方案数目区间dp与高精度的结合高维区间dp问题一般区间dp有

浅浅的花香味﹌/ 2022年09月12日 12:54/ 0 赞/ 188 阅读

相关 51nod 1002数塔取数 dp

一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

不念不忘少年蓝@/ 2022年08月20日 13:11/ 0 赞/ 114 阅读

相关 nyoj 1111 游戏人生【区间dp】

题目：[nyoj 1111 游戏人生 ][nyoj 1111 _] 题意：在一条直线上有n只狼，每只狼有自己的攻击力和辅助攻击，辅助攻击对旁边的两只狼有，问怎样的一

淩亂°似流年/ 2022年08月10日 11:42/ 0 赞/ 114 阅读

相关取数游戏

题目描述: > 给定两个长度为n的整数列A和B，每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax，则第i次取走的数的价值vi=bi⋅a

Love The Way You Lie/ 2022年06月03日 10:26/ 0 赞/ 152 阅读

相关方格取数（状压DP）

include<cstdio> include<iostream> include<algorithm> using namespace std

系统管理员/ 2022年05月28日 07:55/ 0 赞/ 170 阅读

相关区间dp入门

概念：区间DP就是区间上的DP，先算出小区间的最优解，再由小区间合并推出大区间的最优解。典例：一、石子合并。 1.[51Nod 1021 石子归并]

深藏阁楼爱情的钟/ 2022年03月19日 07:07/ 0 赞/ 249 阅读

相关『金字塔区间dp』

-------------------- 金字塔 Description 虽然探索金字塔是极其老套的剧情，但是这一队探险家还是到了某金字塔脚下。经过多年的研究，

傷城~/ 2021年12月21日 21:09/ 0 赞/ 246 阅读

相关区间dp

让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小

小鱼儿/ 2021年11月26日 19:50/ 0 赞/ 377 阅读