2020 银川 B(dp好难捏)

题目
题意: 一个长度为n的数组，分成k个不相交的子段，每个子段的贡献是其中的最大值-最小值，求最大贡献是多少。 n = 1e4
思路: 区间dp，然后发现n^3，寄。坐牢一个多小时也没看出来怎么做。题解很妙，把问题给转化了，相当于把每个数前搞个正负号，某一段的贡献则是开第三维来表示状态。fi,j,k表示前i个数，分成j段，然后当前第j段已经选了+、-，只选了+，只选了-。(也可以再加上什么都不选，也可以用前j-1段已经选了+、-来代替)
然后考虑状态转移。
0表示当前这一段已经选了+、-
1表示只选了+
2表示只选了-
0可以由1和2推得，也由前一个状态顺延(第i个数不选)，也可以使第i个数单独成一段。
1可以由前j-1段选了+、-推得，也可以由前一个状态顺延(第i个数不选)
2也可以由前j-1段选了+、-推得，也可以由前一个状态顺延(第i个数不选)
代码:

#include
using namespace std;
typedef long long ll;
const int N = 1e4+2;
ll f[2][N][3];
ll a[N];
int n;
void solve()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	memset(f,-0x3f,sizeof(f));
	f[0][0][0] = f[1][0][0] = 0;
	int wh = 1; //�����ĵ�һά 
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=i;++j)
		{
//			f[i][j][0] = max({f[i][j][0],f[i-1][j][1]-a[i],f[i-1][j][2]+a[i],f[i-1][j][0],f[i-1][j-1][0]});
//			f[i][j][1] = max({f[i][j][1],f[i-1][j][1],f[i-1][j-1][0]+a[i]});
//			f[i][j][2] = max({f[i][j][2],f[i-1][j][2],f[i-1][j-1][0]-a[i]});
			f[wh][j][0] = max({f[wh^1][j][1]-a[i],f[wh^1][j][2]+a[i],f[wh^1][j][0],f[wh^1][j-1][0]});
			f[wh][j][1] = max({f[wh^1][j][1],f[wh^1][j-1][0]+a[i]});
			f[wh][j][2] = max({f[wh^1][j][2],f[wh^1][j-1][0]-a[i]});
		}
		wh ^= 1;
	}
	wh ^= 1;
	for(int i=1;i<=n;++i)
	{
		printf("%lldn",f[wh][i][0]);
	} 
}
signed main(void)
{
	solve();
	return 0;
}