题目: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[];
}

最新文章

  1. JavaScript闭包之“词法作用域”
  2. 俄罗斯画师Mikhail Rakhmatullin作品
  3. consul笔记
  4. 【linux】VMware12.0安装
  5. html之head,base,meta,title
  6. Maven exclusion
  7. 自动回复消息-微信公众平台开发4(asp.net)
  8. ioctl用法详解 (网络)
  9. solaris bind 符号未定义
  10. 同时存在两个或多个homestead 虚拟box
  11. mac下设置maven环境
  12. visual studio 生成后事件 Post-Build Event
  13. MyEclipse10
  14. laravel框架安装Curl扩展
  15. java中移位运算
  16. dubbo监控中心---dubbo-admin
  17. [20171120]关于find 软连接问题.txt
  18. 清理solaris /var/mail/下的邮件文件
  19. vue set
  20. Token的生成和检验

热门文章

  1. JVisualVM 模拟一次内存泄漏场景分析
  2. Wildfly安装以及集成idea(mac)
  3. postman测试wsdl类型接口
  4. 【ABAP系列】SAP ABAP与Java数据类型的对应关系
  5. Amber
  6. Scala操作外部数据
  7. Tcp协议介绍
  8. Spring Boot 1.x 正式退役,2.x大步向前!
  9. jquery 操作select,checkbox,radio (整理)
  10. git-ssh-keygen