当前位置:网站首页>(POJ - 3186) treatments for the cows (interval DP)
(POJ - 3186) treatments for the cows (interval DP)
2022-07-06 16:23:00 【AC__ dream】
Topic link :3186 -- Treats for the Cows
The question : Here you are. n Numbers that have been arranged , Each time you can take out the leftmost number or the rightmost number , altogether n Take the next time . Suppose you i The number taken next is x, You can get i*x The value of . You need to plan the retrieval sequence , Maximize the total value obtained .
analysis : This problem is easy to be mistaken for greed , Select the minimum value that can be selected each time , Such greedy thinking is wrong .
The following is the analysis of the correct idea :
We set up dp[i][j] It means to take it out from the left i Take them out from the right j In all cases, the result is the maximum , This state can be transferred from two states , One is dp[i-1][j], That is, take it out from the left i-1 Take them out from the right j Circumstances , That is to say, the next number we want to take is i Number , The other is dp[i][j-1], That is, take it out from the left i Take them out from the right j-1 Circumstances , Then the next number we want to take is number n-j+1 Number. , It can only be transferred by these two situations , Then the state transition equation is easy to write , Namely
for(int i=0;i<=n;i++)
for(int j=0;i+j<=n;j++)
{
if(i>0) dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i]*(i+j));// Currently selected No i Elements
if(j>0) dp[i][j]=max(dp[i][j],dp[i][j-1]+a[n-j+1]*(i+j));// Currently selected No n-j+1 Elements
}
Attention should be paid to the boundary problem , Nothing else , The complete code is attached below :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=2003;
int dp[N][N];//dp[i][j] It means taking from the left i The number is taken from the right j The maximum number of
int a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=0;i<=n;i++)
for(int j=0;i+j<=n;j++)
{
if(i>0) dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i]*(i+j));// Currently selected No i Elements
if(j>0) dp[i][j]=max(dp[i][j],dp[i][j-1]+a[n-j+1]*(i+j));// Currently selected No n-j+1 Elements
}
int ans=0;
for(int i=0;i<=n;i++)
ans=max(ans,dp[i][n-i]);
printf("%d",ans);
return 0;
}
边栏推荐
- 1855. Maximum distance of subscript alignment
- Generate random password / verification code
- HDU - 6024 building shops (girls' competition)
- 浏览器打印边距,默认/无边距,占满1页A4
- Codeforces Round #802(Div. 2)A~D
- (POJ - 3579) median (two points)
- Effet d'utilisation, déclenché lorsque les composants de la fonction sont montés et déchargés
- 300th weekly match - leetcode
- C language learning notes
- Opencv learning log 27 -- chip positioning
猜你喜欢
QT实现窗口置顶、置顶状态切换、多窗口置顶优先关系
Vs2019 initial use
(POJ - 3685) matrix (two sets and two parts)
快速转 TypeScript 指南
Configuration du cadre flask loguru log Library
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
(POJ - 3579) median (two points)
OneForAll安装使用
409. Longest palindrome
pytorch提取骨架(可微)
随机推荐
300th weekly match - leetcode
628. Maximum product of three numbers
Configuration du cadre flask loguru log Library
C language must memorize code Encyclopedia
Codeforces round 797 (Div. 3) no f
F - birthday cake (Shandong race)
input 只能输入数字,限定输入
树莓派4B安装opencv3.4.0
Frida hook so layer, protobuf data analysis
Programmers, what are your skills in code writing?
2027. Minimum number of operations to convert strings
What is the difficulty of programming?
The "sneaky" new asteroid will pass the earth safely this week: how to watch it
Kubernetes cluster deployment
Educational Codeforces Round 130 (Rated for Div. 2)A~C
Specify the format time, and fill in zero before the month and days
875. 爱吃香蕉的珂珂 - 力扣(LeetCode)
Auto. Getting started with JS
C language is the watershed between low-level and high-level
Codeforces Round #802(Div. 2)A~D