Problem Description

Home 現在給你一個序列要求你將這個序列拆成恰好兩個子序列。且使得兩個子序列的抖動系數之和最大。

對于一個序列c1,c2,c3，……cm. 其抖動系數=|c1-c2|+|c2-c3|+……+|cm-1-cm|

Input

單組數據，一個行是一個整數n.代表序列長度。

接下一行來有n個整數，a1,a2,a3,……an 代表這個序列

2<=n<=1000

1<=ai<=1e6

Output

輸出一行代表在最優的拆分方案下，最大的抖動系數之和。注意其中任意一個子序列都不可以為空

?

思路：我們把dp[i][j]視為以i和j結尾的兩列的最大值。

我們在放a[i]的時候可以放在i - 1后面，這時就是i和j結尾；或者放在i - 1前的任意一個位置j后面，這時就是i - 1和i結尾，特別的，當i是第一個數時加0。

代碼：

#include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<sstream> #include<iostream> #include<algorithm> #define P pair<int,int> typedef long long ll; using namespace std; const int maxn = 1000 + 10; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; int dp[maxn][maxn]; //以i和j結尾的最大值 int a[maxn]; int main(){int n;scanf("%d" ,&n);for(int i = 1; i <= n; i++)scanf("%d", &a[i]);for(int i = 2; i <= n; i++){for(int j = 0; j < i - 1; j++){a[0] = a[i];dp[i][j] = max(dp[i][j], dp[i - 1][j] + abs(a[i] - a[i - 1]));dp[i][i - 1] = max(dp[i][i - 1], dp[i - 1][j] + abs(a[i] - a[j]));}}int ans = 0;for(int i = 1; i < n; i++)ans = max(ans, dp[n][i]);printf("%d\n", ans);return 0; }

?

轉載于:https://www.cnblogs.com/KirinSB/p/10549219.html

總結

以上是生活随笔為你收集整理的FJUT Home_W的拆分序列（DP）题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。