POJ 3186

系统管理员 2023-08-17 16:37 56阅读 0赞

题意略。

思路：有一点区间dp的意思。

我令dp\[ i \]\[ j \]表示：区间\[1 , i\]和区间\[j , N\]按某种顺序插值排好，所能获得的最大值。

状态转移方程：dp\[ i \]\[ j \] = max(dp\[i - 1\]\[ j \] + v\[ i \] \* (i + N - j + 1) , dp\[ i \]\[ j + 1 \] + v\[ j \] \* (i + N - j + 1))。

代码如下：

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn = 2005;
    const int F = 0x3f;
    const int INF = 0x3f3f3f3f;
    
    int N,v[maxn],dp[maxn][maxn];
    
    int main(){
        while(scanf("%d",&N) == 1){
            for(int i = 1;i <= N;++i) scanf("%d",&v[i]);
            memset(dp,-1,sizeof(dp));
            
            dp[0][N + 1] = 0;
            for(int i = 0;i <= N;++i){
                for(int j = N + 1;j >= 1;--j){
                    if(i == 0 && j == N + 1) continue;
                    int part1 = i - 1 >= 0 ? dp[i - 1][j] + v[i] * (i + N - j + 1) : -1;
                    int part2 = j <= N ? dp[i][j + 1] + v[j] * (i + N - j + 1) : -1;
                    dp[i][j] = max(part1,part2);
                }
            }
            int ans = 0;
            for(int i = 0;i <= N;++i) ans = max(ans,dp[i][i + 1]);
            printf("%d\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/tiberius/p/11291730.html

发表评论取消回复

表情：

评论列表（有 0 条评论，56人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3186

题意略。思路：有一点区间dp的意思。我令dp\[ i \]\[ j \]表示：区间\[1 , i\]和区间\[j , N\]按某种顺序插值排好，所能获得的最大值。状

系统管理员/ 2023年08月17日 16:37/ 0 赞/ 57 阅读

相关 poj 1064 java_poj1064

Cable master Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 15127 Accept

r囧r小猫/ 2022年11月05日 03:30/ 0 赞/ 133 阅读

相关【POJ】：POJ 3984

题目链接：[http://poj.org/problem?id=3984][http_poj.org_problem_id_3984] 题目解析：这题算是搜索里面的简单题了吧

Myth丶恋晨/ 2022年08月23日 04:50/ 0 赞/ 172 阅读

相关 Poj1129

当一个广播电台在一个非常大的地区，广播站会用中继器来转播信号以使得每一个接收器都能接收到一个强烈的信号。然而，每个中继器必须慎重选择使用，使相邻的中继器不互相干扰。如果相邻的中

小鱼儿/ 2022年08月05日 08:52/ 0 赞/ 149 阅读

相关 poj1004

\include <iostream> using namespace std; int main() \{ int i;

缺乏、安全感/ 2022年06月16日 08:27/ 0 赞/ 156 阅读

相关 poj3006

\include <iostream> \include <cmath> using namespace std; int pansu(int x) \{

超、凢脫俗/ 2022年06月15日 03:16/ 0 赞/ 106 阅读

相关【区间dp】Treats for the Cows POJ - 3186

Think: 1知识点：区间dp 2题意：给定一个长度为n的序列，从1开始取n次，每次可以选取第一个结点或者最后一个结点，每次获取的价值为当前次数乘以选取的结点数值，询

梦里梦外;/ 2022年06月10日 03:51/ 0 赞/ 139 阅读

相关 poj1321+poj2251

poj1321代码实现（dfs）： include <iostream> include <string.h> using namespace std

心已赠人/ 2022年05月30日 04:08/ 0 赞/ 156 阅读

相关 poj1423

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] [http://acm.pku.edu.cn/JudgeOnline/problem?

短命女/ 2022年01月15日 10:07/ 0 赞/ 162 阅读

相关 poj1007

1．链接地址 [https://vjudge.net/problem/POJ-1007][https_vjudge.net_problem_POJ-1007] 2．问题描述

深藏阁楼爱情的钟/ 2021年11月23日 15:38/ 0 赞/ 194 阅读