洛谷 P3009 [USACO11JAN]利润Profits

2024-09-05 07:31:23

嗯...

题目链接：https://www.luogu.org/problemnew/show/P3009

这是DP的另一个功能，求最大子段和（最大子段和模板：https://www.luogu.org/problemnew/show/P1115），动态转移方程为：

 dp[i] = max(a[i], dp[i - ] + a[i]);

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int maxn = ;

 int dp[maxn], p[maxn];

 int main(){

     int n;

     scanf("%d", &n);

     for(int i = ; i <= n; i++)

         scanf("%d", &p[i]);

     for(int i = ; i <= n; i++)

         dp[i] = max(dp[i - ] + p[i], p[i]);

     sort(dp + , dp +  + n);

     printf("%d", dp[n]);

 }

AC代码

最新文章

热门文章