AcWing 312. 乌龟棋 (简单DP)打卡
2024-10-07 14:14:29
题目:https://www.acwing.com/problem/content/description/314/
题意:有一段路,每个格子都有个价值,然后有m张卡牌,四种类型,走1,2,3,4步,然后输入保证正好把所有卡牌用完到达终点,求最大价值
思路:保证全部用完,只是顺序不一样得到的价值不一样,首先分别是四种类型的卡牌,对于这种要在一个点找最优的肯定是dp,我开始想的是五维状态 dp[n][a][b][c][d],代表第n个格子,然后a,b,c,d四种类型卡牌的数量, 然后代表我用a,b,c,d类型这么多张卡牌的价值最大是多少但是这样的话复杂度在 O(320*40^4),时间就超时了,实际上我们可以用使用了四种类型的卡牌数量来得到当前走到哪个位置,然后用下面四种状态分别转移然后就能得到答案
#include<bits/stdc++.h>
#define maxn 100005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll dp[][][][];
ll n,m,a[];
ll e[],x;
int main(){
cin>>n>>m;
for(int i=;i<n;i++){
cin>>a[i];
}
for(int i=;i<=m;i++){
cin>>x;
e[x]++;
}
for(int A=;A<=e[];A++){
for(int B=;B<=e[];B++){
for(int C=;C<=e[];C++){
for(int D=;D<=e[];D++){
ll v=a[A+*B+*C+*D];
if(A)
dp[A][B][C][D]=max(dp[A][B][C][D],dp[A-][B][C][D]+v);
if(B)
dp[A][B][C][D]=max(dp[A][B][C][D],dp[A][B-][C][D]+v);
if(C)
dp[A][B][C][D]=max(dp[A][B][C][D],dp[A][B][C-][D]+v);
if(D)
dp[A][B][C][D]=max(dp[A][B][C][D],dp[A][B][C][D-]+v);
}
}
}
}
cout<<dp[e[]][e[]][e[]][e[]]+a[];
}
最新文章
- JavaScript闭包之“词法作用域”
- 俄罗斯画师Mikhail Rakhmatullin作品
- consul笔记
- 【linux】VMware12.0安装
- html之head,base,meta,title
- Maven exclusion
- 自动回复消息-微信公众平台开发4(asp.net)
- ioctl用法详解 (网络)
- solaris bind 符号未定义
- 同时存在两个或多个homestead 虚拟box
- mac下设置maven环境
- visual studio 生成后事件 Post-Build Event
- MyEclipse10
- laravel框架安装Curl扩展
- java中移位运算
- dubbo监控中心---dubbo-admin
- [20171120]关于find 软连接问题.txt
- 清理solaris /var/mail/下的邮件文件
- vue set
- Token的生成和检验