题意
给一个队列的商品 每天只能拿最左或者最右 商品的价值是自身的价值乘卖出的天数 问最大能卖多少
题解
一开始想的dp复杂了。。实际上就是简单的区间dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long dp[2040][2040];
int treat[2020];
int main(){
int n;
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d", &treat[i]), dp[i][i] = treat[i]*n;
for(int len = 1; len < n; len++){
for(int i = 1; i < n; i++){
int j = i + len;
dp[i][j] = max(dp[i+1][j]+treat[i]*(n-len), dp[i][j-1]+treat[j]*(n-len));
}
}
printf("%lld\n",dp[1][n]);
return 0;
}
|