思路1:背包+状态机
状态表示:f[i][j][k]:第i天时的交易次数<=j且状态为k的所有方案~利润最大(0表示不持股,1表示持股)
状态计算:f[i][j][0] = max(f[i - 1][j][0],f[i - 1][j - 1][1] + w[i]),f[i][j][1] = max(f[i - 1][j][1],f[i - 1][j][0] - w[i])
初始化:
memset(f,-INF,sizeof f);
for(int i = 0;i <= m;i++)
f[0][i][0] = 0;
或
for(int i = 1;i <= m;i++)
f[1][i][1] = -w[1];
f[1][0][1] = -INF;
c++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010,M = 110,INF = 0x3f3f3f3f;
int n,m;
int w[N];
int f[N][M][2];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> w[i];
memset(f,-INF,sizeof f);
for(int i = 0;i <= m;i++)
f[0][i][0] = 0;
for(int i = 1;i <= n;i++)
for(int j = 0;j <= m;j++)
{
f[i][j][0] = f[i - 1][j][0];
if(j) f[i][j][0] = max(f[i][j][0],f[i - 1][j - 1][1] + w[i]);
f[i][j][1] = max(f[i - 1][j][1],f[i - 1][j][0] - w[i]);
}
int res = f[n][m][0];
cout << res << endl;
return 0;
}
或
#include <bits/stdc++.h>
using namespace std;
const int N = 100010,M = 110,INF = 0x3f3f3f3f;
int n,m;
int w[N];
int f[N][M][2];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> w[i];
for(int i = 1;i <= m;i++)
f[1][i][1] = -w[1];
f[1][0][1] = -INF;
for(int i = 2;i <= n;i++)
for(int j = 0;j <= m;j++)
{
f[i][j][0] = f[i - 1][j][0];
if(j) f[i][j][0] = max(f[i][j][0],f[i - 1][j - 1][1] + w[i]);
f[i][j][1] = max(f[i - 1][j][1],f[i - 1][j][0] - w[i]);
}
int res = f[n][m][0];
cout << res << endl;
return 0;
}
思路2:状态机
状态表示:f[i][j][k]:第i天的交易次数恰好为j且对应状态为k的所有方案~利润最大(0表示不持股,1表示持股)
状态计算:状态计算:f[i][j][0] = max(f[i - 1][j][0],f[i - 1][j - 1][1] + w[i]),f[i][j][1] = max(f[i - 1][j][1],f[i - 1][j][0] - w[i])
初始化:
memset(f,-INF,sizeof f);
f[1][0][1] = -w[1],f[1][0][0] = 0;
或
memset(f,-INF,sizeof f);
f[0][0][0] = 0;
c++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010,M = 110,INF = 0x3f3f3f3f;
int n,m;
int w[N];
int f[N][M][2];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> w[i];
memset(f,-INF,sizeof f);
f[1][0][1] = -w[1],f[1][0][0] = 0;
for(int i = 2;i <= n;i++)
for(int j = 0;j <= m;j++)
{
f[i][j][0] = f[i - 1][j][0];
if(j) f[i][j][0] = max(f[i][j][0],f[i - 1][j - 1][1] + w[i]);
f[i][j][1] = max(f[i - 1][j][1],f[i - 1][j][0] - w[i]);
}
int res = 0;
for(int i = 1;i <= m;i++)
res = max(res,f[n][i][0]);
cout << res << endl;
return 0;
}
或
#include <bits/stdc++.h>
using namespace std;
const int N = 100010,M = 110,INF = 0x3f3f3f3f;
int n,m;
int w[N];
int f[N][M][2];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> w[i];
memset(f,-INF,sizeof f);
f[0][0][0] = 0;
for(int i = 1;i <= n;i++)
for(int j = 0;j <= m;j++)
{
f[i][j][0] = f[i - 1][j][0];
if(j) f[i][j][0] = max(f[i][j][0],f[i - 1][j - 1][1] + w[i]);
f[i][j][1] = max(f[i - 1][j][1],f[i - 1][j][0] - w[i]);
}
int res = 0;
for(int i = 1;i <= m;i++)
res = max(res,f[n][i][0]);
cout << res << endl;
return 0;
}