首页 > 代码库 > UVALive 6430 （水dp）

UVALive 6430 （水dp）

2024-07-17 23:43:20   220人阅读

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4441

 

题意：有n个靶子，每个靶子有3个val，需要满足3钟情况分别得到他们的val。问最大的得分。

sl :很水的dp, 记录下当前的4个状态，分别是，不选，选（左边选右边不选，左边不选右边选，左右多不选，左边右边都选），转移很简单了。

 训练时看错题逗比了半天，逗。

#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int MAX = 1e6+10;
struct node {
    int a,b,c;
}v[MAX];
LL dp[MAX][5];
int main() {
    int n,a,b,c;
    while(scanf("%d",&n)==1) {
        for(int i=1;i<=n;i++) {
            scanf("%d %d %d",&v[i].a,&v[i].b,&v[i].c);
        }
        memset(dp,0,sizeof(dp));
        if(n==1) {
            printf("%d\n",v[1].a);
        }
        else {
            dp[1][0]=0; dp[1][1]=v[1].a; dp[1][2]=v[1].b;
            for(int i=2;i<=n;i++) {
                dp[i][0]=max(dp[i-1][0],max(dp[i-1][3],dp[i-1][1]));
                dp[i][1]=dp[i-1][0]+v[i].a;
                dp[i][2]=dp[i-1][0]+v[i].b;
                dp[i][3]=max(dp[i-1][2]+v[i].b,dp[i-1][4]+v[i].b);
                dp[i][4]=max(dp[i-1][2],dp[i-1][4])+v[i].c;
            }
            LL ans=0;
            ans=max(ans,dp[n][0]); ans=max(ans,dp[n][1]); ans=max(ans,dp[n][3]);
            printf("%d\n",ans);
        }
    }

} 

 


联系
我们