POJ 3186

系统管理员 2023-08-17 16:37 94阅读 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 条评论，94人围观）

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

相关阅读

相关 POJ 3186

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

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

相关 poj 1064 java_poj1064

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

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

相关【POJ】：POJ 3984

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

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

相关 POJ Tautology

Tautology <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

た入场券/ 2022年07月10日 04:16/ 0 赞/ 215 阅读

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

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

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

相关 poj1321+poj2251

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

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

相关 poj1061

构造方程 (x + m \ s) - (y + n \ s) = k \ l(k = 0, 1, 2,...) 变形为 (n-m) \ s + k \ l = x - y。即

你的名字/ 2021年12月14日 00:07/ 0 赞/ 237 阅读

相关【~~~】POJ-1018

\include "stdio.h" int main() \{ int a\[101\]\[202\],num\[101\],n,i,j,k,h,temp

野性酷女/ 2021年12月05日 13:09/ 0 赞/ 257 阅读

相关 poj1007

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

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

相关 poj 1009

参考自大神思路：[POJ 1009][] 首先，暴力必挂，这是题目的善意提醒。于是，一直在想不暴力的各种判断计算方法，关于各种跳跃移动，后来都无奈想用STL。原谅我的

刺骨的言语ヽ痛彻心扉/ 2021年11月02日 00:46/ 0 赞/ 282 阅读