[NOIp2010] luogu P1541 乌龟棋
2024-08-30 07:30:20
英语老师讲 mind map,真想说一句“声微饭否”。为什么wyy的歌词总是快一点点。在报csp。
题目描述
你在一个序列上向正方向行走,起点是 a[0]a[0]a[0]。每一步可以走 1,2,3,41,2,3,41,2,3,4 格,每种步长的使用次数受限,保证用完步数后恰好到达终点。一次行走的得分为经过所有点的权值之和。求最大得分。
Solution
看这个数据范围就知道是 DP 了。
设 f[i][j][k][l]f[i][j][k][l]f[i][j][k][l] 表示使用 i,j,k,li,j,k,li,j,k,l 次 1,2,3,41,2,3,41,2,3,4 步的最大得分。显然你现在的位置是sum=i+2j+3k+4lsum=i+2j+3k+4lsum=i+2j+3k+4l注意特判起点。时间复杂度 O(M4)O(M^4)O(M4),空间复杂度 O(M4)O(M^4)O(M4)。
#include<cstdio>
#include<cstdlib>
#include<cstring>
const int MAXN=45;
int n,m;
int g[5]={0,0,0,0,0},a[400];
int sx;
int f[MAXN][MAXN][MAXN][MAXN];
int max(int x,int y){
return x>y?x:y;
}
int sum(int a,int b,int c,int d){
return a+b+b+c+c+c+d+d+d+d+1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=m;++i){
scanf("%d",&sx);
++g[sx];
}
memset(f,0,sizeof(f));f[0][0][0][0]=a[1];
for(int i=0;i<=g[1];++i)
for(int j=0;j<=g[2];++j)
for(int k=0;k<=g[3];++k)
for(int l=0;l<=g[4];++l){
//这里我打得比较丑
if(i)
f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[sum(i,j,k,l)]);
if(j)
f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[sum(i,j,k,l)]);
if(k)
f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[sum(i,j,k,l)]);
if(l)
f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[sum(i,j,k,l)]);
}
printf("%d",f[g[1]][g[2]][g[3]][g[4]]);
}
最新文章
- Windbg Extension NetExt 使用指南 【3】 ---- 挖掘你想要的数据 Managed Heap
- awk中的system和getline的用法
- P1905生活大爆炸版 石头剪刀布
- OI总结(垃圾排版就忽略了吧)
- 关于引用类型作为参数加上ref与不加ref的区别
- Ajax跨域请求ashx文件与Webservice文件
- 夺命雷公狗---微信开发62----所以memcache对access_token进行全局缓存优化
- awesome-very-deep-learning
- BZOJ 2004 Bus 公交线路(矩阵)
- 并发视频,怎么hold住高并发
- Python 2.7 学习笔记 条件与循环语句
- C#实现树的双亲表示法
- Service Manager 2012
- SQL Server 安装报错找不到vc_red.msi
- IOS中多线程的总结
- 阿里云RDS数据库改造迁移方案
- Cleanmymac X好不好用?
- iOS开发中id、NSObject *、id、instancetype四者有什么区别?
- IDEA 现有项目连接SVN
- 安全紧急预警-防范新型 Sigrun 勒索病毒
热门文章
- master.TableNamespaceManager: Namespace table not found. Creating...
- 大数据平台搭建 - cdh5.11.1 - hadoop集群安装
- 干货| 外卖点餐系统(App及后台)
- 由于找不到opencv_world***d.dl,无法继续执行代码。重新安装程序可能会解决此问题。关于opencv使用imshow函数闪退解决方法等问题
- 基于Asp.Net Core MVC和AdminLTE的响应式管理后台之侧边栏处理
- [LeetCode] 由 “找零钱"; 所想
- (七十三)c#Winform自定义控件-资源加载窗体
- java selenium 自动化笔记-不是0基础,至少有java基础
- win10 更新之后,软件路径被改为*
- 性能优化:虚拟列表,如何渲染10万条数据的dom,页面同时不卡顿