nyoj 1111 游戏人生【区间dp】

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

题目：[nyoj 1111 游戏人生 ][nyoj 1111 _]

题意：在一条直线上有n只狼，每只狼有自己的攻击力和辅助攻击，辅助攻击对旁边的两只狼有，问怎样的一个杀怪顺序才能使得花费最小。

分析：这是北京现场赛的题目，当时一眼看出来是区间dp，但是没有考虑计算一个区间之后两边的辅助攻击，也是很有没有做dp题目了。

定义：dp【i】【j】为打从区间 i -- j 的怪的伤害，然后转移方程dp【i】【j】 = min（dp【i】【j】 ，dp【i】【k-1】 + a【k】 + dp【k+1】【j】） + fu【i-1】【j+1】

一直没有考虑到后面加的一部分，所以代码就很好写了。

AC代码：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define N 350
    int dp[N][N];
    int b[N],a[N];
    int main()
    {
        int n,T;
        scanf("%d",&T);
        for(int cas = 1;cas<=T;cas++)
        {
            scanf("%d",&n);
            for(int i=1;i<=n;i++){
                scanf("%d",&a[i]);
            }
            for(int i=1; i<=n; i++)
                scanf("%d",&b[i]);
            b[0]=b[n+1]=0;
            memset(dp,0,sizeof(dp));
            int i,j,l,k;
    		for(l = 1; l <= n; ++l)
    		{
    			for(i = 1; i <= n - l + 1; ++i)
    			{
    				j = i + l - 1;
    				dp[i][j] = 2100000000;
                    for(int k=i; k<=j; k++)
                    {
                        dp[i][j]=min(dp[i][j],dp[i][k-1]+a[k]+dp[k+1][j]);
                    }
                    dp[i][j]+=b[i-1]+b[j+1];
    			}
    		}
    		printf("Case #%d: %d\n",cas, dp[1][n]);
        }
        return 0;
    }

[nyoj 1111 _]: http://acm.nyist.net/JudgeOnline/problem.php?pid=1111

发表评论取消回复

表情：

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

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

相关阅读

相关【区间DP】取数游戏

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

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

相关 nyoj 737 石子合并（一）（区间dp）

石子合并（一）时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆

爱被打了一巴掌/ 2024年02月17日 20:53/ 0 赞/ 29 阅读

相关区间dp

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

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

相关 Brackets (区间DP)

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

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

相关区间dp问题

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

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

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

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

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

相关 NYOJ 304 DP

节能时间限制： 1000 ms | 内存限制： 65535 KB 难度： 5 描述 Dr.Kong设计的机器人卡多越来越聪明。最近市政公司交给卡多一项任务，每

Myth丶恋晨/ 2022年06月17日 12:23/ 0 赞/ 144 阅读

相关算法学习之区间dp加NYOJ-737—石子合并

区间DP 顾名思义，指的是每个区间上的dp，它的主要思想就是先在小区间进行dp得到最优解，然后再利用小区间的最优解合并求大区间的最优解。模板代码： //先对

冷不防/ 2022年05月18日 07:23/ 0 赞/ 207 阅读

相关区间dp入门

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

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

相关区间dp

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

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