P1541-乌龟棋

Love The Way You Lie 2023-06-01 08:51 5阅读 0赞

1 #pragma GCC optimize("Ofast")
     2 #include <bits/stdc++.h>
     3 #define maxn 13003
     4 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     5 typedef long long ll;
     6 using namespace std;
     7 
     8 inline ll read()
     9 {
    10     ll ans = 0;
    11     char ch = getchar(), last = ' ';
    12     while(!isdigit(ch)) last = ch, ch = getchar();
    13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    14     if(last == '-') ans = -ans;
    15     return ans;
    16 }
    17 inline void write(ll x)
    18 {
    19     if(x < 0) x = -x, putchar('-');
    20     if(x >= 10) write(x / 10);
    21     putchar(x % 10 + '0');
    22 }
    23 
    24 int N,M;
    25 int ip[400];
    26 int dp[41][41][41][41];
    27 int num[5];
    28 int main()
    29 {
    30     N = read(),M = read();
    31     _for(i,1,N+1)
    32         ip[i] = read();
    33     
    34     _for(i,1,M+1)
    35         num[read()] ++;
    36     
    37     dp[0][0][0][0] = ip[1];
    38     _for(a,0,num[1]+1)
    39         _for(b,0,num[2]+1)
    40             _for(c,0,num[3]+1)
    41                 _for(d,0,num[4]+1)
    42                 {
    43                     int r = 1+a+2*b+3*c+4*d;
    44                     if(a) dp[a][b][c][d] = max(dp[a][b][c][d],dp[a-1][b][c][d]+ip[r]);
    45                     if(b) dp[a][b][c][d] = max(dp[a][b][c][d],dp[a][b-1][c][d]+ip[r]);
    46                     if(c) dp[a][b][c][d] = max(dp[a][b][c][d],dp[a][b][c-1][d]+ip[r]);
    47                     if(d) dp[a][b][c][d] = max(dp[a][b][c][d],dp[a][b][c][d-1]+ip[r]);
    48                 }
    49     write(dp[num[1]][num[2]][num[3]][num[4]]);
    50     return 0;
    51 }

转载于:https://www.cnblogs.com/Asurudo/p/11350648.html

发表评论取消回复

表情：

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

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

相关阅读

相关【DP】乌龟棋

这状态设计的真的牛逼本来想了个暴力DP，前i个数选了j个卡片，选的是第k个卡片，然后搞个状压记录选了哪几种卡片，因为卡片一共就4种但是它说的不能选是指同一种是可以重复选

「爱情、让人受尽委屈。」/ 2024年03月24日 10:23/ 0 赞/ 44 阅读

相关洛谷——P1838 三子棋I

P1838 三子棋I 题目描述小a和uim喜欢互相切磋三子棋。三子棋大家都玩过是吗？就是在九宫格里面OOXX（别想歪了），谁连成3个就赢了。由于小a比较愚蠢，

青旅半醒/ 2023年10月02日 12:06/ 0 赞/ 11 阅读

相关 P1541-乌龟棋

1 pragma GCC optimize("Ofast") 2 include <bits/stdc++.h> 3 define maxn 130

Love The Way You Lie/ 2023年06月01日 08:51/ 0 赞/ 6 阅读

相关 JAVA小乌龟游泳_描写乌龟游泳的作文

描写乌龟游泳的作文关于描写乌龟游泳的作文大家了解过多少呢？可能很多人都不是很清楚，下面就是小编分享的描写乌龟游泳的作文范文，一起来看一下吧。 ![944fb73ef3c6

青旅半醒/ 2022年11月10日 05:47/ 0 赞/ 209 阅读

相关 java - 小乌龟

1.Java与C++的不同之一就是: Java的main函数写在一个类中，而C++不是 2.java与C++的不同之二就是：Java中不允许多继承，即为单根结构，最大

逃离我推掉我的手/ 2022年08月07日 00:25/ 0 赞/ 193 阅读

相关【基础练习】【背包DP】codevs1068 乌龟棋题解

题目来自2010NOIP提高组题目描述 Description 小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。乌龟棋的棋盘是一行N个格子，每个格子上一个分数

港控/mmm°/ 2022年08月03日 23:59/ 0 赞/ 171 阅读

相关 HDU 1541 Stars（树状数组）

> Stars Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others

不念不忘少年蓝@/ 2022年06月16日 04:49/ 0 赞/ 178 阅读

相关 HDU 1541 Stars（树状数组||线段树）

Astronomers often examine star maps where stars are represented by points on a plane and

爱被打了一巴掌/ 2022年06月12日 00:20/ 0 赞/ 241 阅读

相关洛谷P1541 乌龟棋

题目背景小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。题目描述乌龟棋的棋盘是一行N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一的起点，第N格是

偏执的太偏执、/ 2022年05月27日 12:27/ 0 赞/ 118 阅读

相关 Stars HDU - 1541

[HDU - 1541 ][HDU - 1541] 思路：二维偏序，一维排序，一维树状数组查询即可。 include<bits/stdc++.h> usin

深碍√TFBOYSˉ_/ 2022年01月06日 12:47/ 0 赞/ 179 阅读