洛谷 1541 NOIp2010提高组 乌龟棋
2024-08-30 22:38:50
【题解】
很容易想到这是一个DP,f[i][j][k][l]表示4种卡片分别用了多少张,那么转移方程就是f[i][j][k][l]=Max(f[i-1][j][k][l],f[i][j-1][k][l],f[i][j][k-1][l],f[i][j][k][l-1])+a[i+j*2+k*3+l*4+1].
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define rg register
#define N 400
using namespace std;
int n,m,cnt[],f[][][][],a[N];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
int main(){
n=read(); m=read();
for(rg int i=;i<=n;i++) a[i]=read();
for(rg int i=;i<=m;i++) cnt[read()]++;
for(rg int i=;i<=cnt[];i++)
for(rg int j=;j<=cnt[];j++)
for(rg int k=;k<=cnt[];k++)
for(rg int l=;l<=cnt[];l++){
int pos=i+(j<<)+(k*)+(l<<)+;
if(i>=)f[i][j][k][l]=max(f[i][j][k][l],f[i-][j][k][l]);
if(j>=)f[i][j][k][l]=max(f[i][j][k][l],f[i][j-][k][l]);
if(k>=)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-][l]);
if(l>=)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-]);
f[i][j][k][l]+=a[pos];
}
printf("%d\n",f[cnt[]][cnt[]][cnt[]][cnt[]]);
return ;
}
最新文章
- DDD 领域驱动设计-两个实体的碰撞火花
- CPU阿甘:函数调用的秘密
- cocos2d学习笔记
- Java 线程池的介绍以及工作原理
- Spring 框架整理
- Android 百度地图 SDK v3.0.0 (三) 加入覆盖Marker与InfoWindow使用
- 优化之sitemap+RSS
- java集合(1)- 类底层数据结构分析
- BZOJ 1758: [Wc2010]重建计划 [暂时放弃]
- PHP为前端CSS和JS增加时间戳版本号
- c/c++ new delete初探
- ACM-ICPC 2018 焦作赛区网络预赛 K Transport Ship (多重背包)
- CSS布局学习(三) - Normal Flow 正常布局流(官网直译)
- cordic——sincos
- JavaScript Window History 浏览器的历史
- linux手工释放内存
- SNMP TRAP报文解析
- (考研)PV操作和信号量
- LintCode2016年8月8日算法比赛----子树
- Hibernate 注解方式配置