P1541 [NOIP2010 提高组] 乌龟棋

zhoukeyi · 2022-11-10 22:56:10 · 题解

P1541 [NOIP2010 提高组] 乌龟棋

一，解析

这道题应该是线性dp，而且是逆推

六要素

1，状态

f[i][j][k][p]是四种卡牌用的张数

2，阶段

阶段就是选了哪几张卡牌为阶段

3，决策

决策就是用哪张卡牌

4，阶状态转移方程

if(whq!=0) lft[whq][xjz][zky][lyj]=max(lft[whq][xjz][zky][lyj],lft[whq-1][xjz][zky][lyj]+a[ysc]);
if(xjz!=0) lft[whq][xjz][zky][lyj]=max(lft[whq][xjz][zky][lyj],lft[whq][xjz-1][zky][lyj]+a[ysc]);
if(zky!=0) lft[whq][xjz][zky][lyj]=max(lft[whq][xjz][zky][lyj],lft[whq][xjz][zky-1][lyj]+a[ysc]);
if(lyj!=0) lft[whq][xjz][zky][lyj]=max(lft[whq][xjz][zky][lyj],lft[whq][xjz][zky][lyj-1]+a[ysc]);                   

5，边界值

边界值要注意的就是 f要初始化

lft[0][0][0][0]=a[1];

6，目标值

直接lft[w[1]][w[2]][w[3]][w[4]]就行了

二，代码

#include<bits/stdc++.h>
using namespace std;
int a[355],w[125];
int lft[41][41][41][41];
int main(){
    int n,m,fbi=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>fbi;
        w[fbi]++;
    }
    lft[0][0][0][0]=a[1];//初始化
    for(int whq=0;whq<=w[1];whq++){
        for(int xjz=0;xjz<=w[2];xjz++){
            for(int zky=0;zky<=w[3];zky++){
                for(int lyj=0;lyj<=w[4];lyj++){
                    int ysc=1+whq+xjz*2+zky*3+lyj*4;//一共移动了几步
                    if(whq!=0) lft[whq][xjz][zky][lyj]=max(lft[whq][xjz][zky][lyj],lft[whq-1][xjz][zky][lyj]+a[ysc]);
                    if(xjz!=0) lft[whq][xjz][zky][lyj]=max(lft[whq][xjz][zky][lyj],lft[whq][xjz-1][zky][lyj]+a[ysc]);
                    if(zky!=0) lft[whq][xjz][zky][lyj]=max(lft[whq][xjz][zky][lyj],lft[whq][xjz][zky-1][lyj]+a[ysc]);
                    if(lyj!=0) lft[whq][xjz][zky][lyj]=max(lft[whq][xjz][zky][lyj],lft[whq][xjz][zky][lyj-1]+a[ysc]);               
                }
            }
        }
    }
    cout<<lft[w[1]][w[2]][w[3]][w[4]];//全用上的情况
    return 0;
}