线性dp

103 阅读 0 评论 68 点赞

我是靠谱客的博主香蕉海燕，这篇文章主要介绍线性dp，现在分享给大家，希望可以做个参考。

OJ题目：click here~

题目分析：股票买卖。给股票价格。先买后卖，只能手持一股。求最大收益。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LL dp[1002][1002];
int main(){
int i , j , n , m, k , x[1002] ;
//freopen("in.txt" , "r" , stdin);
while(scanf("%d%d",&n,&m) != EOF){
for(i = 1;i <= n;i++)
scanf("%d",&x[i]);
memset(dp , 0 , sizeof(dp));
LL mx = 0;
for(j = 1;j <= m;j++){
mx = dp[1][j - 1] - x[1];
for(i = 1;i <= n;i++){
dp[i][j] = max(dp[i - 1][j] , mx + x[i]);
mx = max(mx , dp[i][j - 1] - x[i]);
}
}
cout << dp[n][m]<<endl;
}
}