标签：882 sum Codeforces al test each div.2 villagers dp

Smiling&Weeping

　　　　　　　　　　　　　　　　　　　　　----总有人间一两风，填我十万八千梦

A. The Man who became a God time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

 

Kars is tired and resentful of the narrow mindset of his village since they are content with staying where they are and are not trying to become the perfect life form. Being a top-notch inventor, Kars wishes to enhance his body and become the perfect life form. Unfortunately, n� of the villagers have become suspicious of his ideas. The i�-th villager has a suspicion of ai�� on him. Individually each villager is scared of Kars, so they form into groups to be more powerful.

The power of the group of villagers from l� to r� be defined as f(l,r)�(�,�) where

 

f(l,r)=|al−al+1|+|al+1−al+2|+…+|ar−1−ar|.�(�,�)=|��−��+1|+|��+1−��+2|+…+|��−1−��|.

 

Here |x−y||�−�| is the absolute value of x−y�−�. A group with only one villager has a power of 00.

Kars wants to break the villagers into exactly k� contiguous subgroups so that the sum of their power is minimized. Formally, he must find k−1�−1 positive integers 1≤r1<r2<…<rk−1<n1≤�1<�2<…<��−1<� such that f(1,r1)+f(r1+1,r2)+…+f(rk−1+1,n)�(1,�1)+�(�1+1,�2)+…+�(��−1+1,�) is minimised. Help Kars in finding the minimum value of f(1,r1)+f(r1+1,r2)+…+f(rk−1+1,n)�(1,�1)+�(�1+1,�2)+…+�(��−1+1,�).

Input

The first line contains a single integer t� (1≤t≤100)(1≤�≤100) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers n,k�,� (1≤k≤n≤100)(1≤�≤�≤100) — the number of villagers and the number of groups they must be split into.

The second line of each test case contains n� integers a1,a2,…,an�1,�2,…,�� (1≤ai≤500)(1≤��≤500) — the suspicion of each of the villagers.

Output

For each test case, output a single integer — the minimum possible value of sum of power of all the groups i. e. the minimum possible value of f(1,r1)+f(r1+1,r2)+…+f(rk−1+1,n)�(1,�1)+�(�1+1,�2)+…+�(��−1+1,�).

   

 

详见：Problem - A - Codeforces

思路：DP分组，使总数和最小，那么我们就定义状态dp[i][j] 代表前i个中分j组时的最小值

然后写出状态方程：dp[i][j] = min(dp[i][j] , dp[l][j-1]+sum[i]-sum[l+1])

这里呢有一些细节，你如sum[i]-sum[l+1] , dp[l][j-1]已经囊括了a0--al的范围了，并且单独一个村庄power=0，因此对于之后，便不必记录al与al+1的关系了，对了还要注意哦：分成k组，只需要划k-1条线即可，那么我们上代码

 1 #include<bits/stdc++.h>
 2 #include<vector>
 3 using namespace std;
 4 int t , n , k, dp[110][110];
 5 int main()
 6 {
 7     scanf("%d",&t);
 8     while(t--)
 9     {
10         memset(dp , 0x3f , sizeof(dp));
11         scanf("%d%d",&n,&k);
12         vector<int> sum(n+10);
13         vector<int> a(n+10);
14         for(int i = 1; i <= n; i++)
15             scanf("%d",&a[i]);
16         dp[1][0] = 0;   dp[0][0] = 0;
17         for(int i = 2; i <= n; i++)
18             sum[i] = sum[i-1] + abs(a[i]-a[i-1]);
19         for(int i = 1; i <= n; i++)
20             dp[i][0] = sum[i];
21         for(int i = 1; i <= n; i++)
22             for(int j = 1; j <= min(i,k-1); j++)　　　　　　　　　　　　　　　　 // 这里需要注意
23                 for(int l = j-1; l < i; l++)
24                     dp[i][j] = min(dp[i][j] , dp[l][j-1]+sum[i]-sum[l+1]); // 关键
25         printf("%d\n",dp[n][k-1]);
26     }
27     return 0;
28 }

؏؏☝ᖗ乛◡乛ᖘ☝؏؏我们下期再见，（づ￣3￣）づ╭❤～you

 

标签：882,sum,Codeforces,al,test,each,div.2,villagers,dp
From： https://www.cnblogs.com/smiling-weeping-zhr/p/17566758.html