【区间DP】取数游戏

我就是我 2024-03-24 10:23 47阅读 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 条评论，47人围观）

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

相关阅读

相关【区间DP】取数游戏

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

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

相关区间dp

概念区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。借鉴大佬总结：[猛戳][Link

Bertha 。/ 2023年07月10日 08:18/ 0 赞/ 37 阅读

相关 Brackets (区间DP)

目录 Brackets (区间DP) 题目题意思路题解 Brackets (区间DP)

绝地灬酷狼/ 2023年06月01日 06:11/ 0 赞/ 30 阅读

相关 51nod 1002数塔取数 dp

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

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

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

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

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

相关【日常学习】【区间DP+高精】codevs1166 矩阵取数游戏题解

题目来自NOIP2007TG3 如果在考场上我现在已经歇菜了吧今天一整天的时间全部投在这道题上，收获不小。先上题目题目描述 Descripti

矫情吗；*/ 2022年08月04日 00:57/ 0 赞/ 21 阅读

相关取数游戏

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

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

相关方格取数（状压DP）

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

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

相关区间dp入门

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

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

相关区间dp

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

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