题解：动态规划

• 题目：
• 解析
  • 部分分
    • 部分分代码（60分）
  • 全部分
    • AC代码

题目：

解析

部分分

这道题首先不考虑优化，我们该怎么写呢？显然，这是一个区间dp，我们可以利用记忆化搜索来写。
1、定义状态：dp[i][j]表示前i头分j段的最小价值。
2、状态转移方程：ans = min(ans,value(x,i) + dfs_dp(i + 1,left - 1));
这个状态转移方程和https://www.cnblogs.com/Crazyman-W/p/14872804.html 这道题十分类似。
3、然后是计算有多少对羊：

int value(int x,int y) {
    int ans = 0;
    memset(sum,0,sizeof(sum));
    int mn = 2e9,mx = 0;
    for(int i = x;i <= y; i++) {
	    sum[a[i]]++;
	    mx = max(mx,a[i]);
	    mn = min(mn,a[i]);
    }
    for(int i = mn;i <= mx; i++) {
	    ans += (sum[a[i]] * (sum[a[i]] - 1) ) / 2; //用排列组合算出每个数有多少对
	    sum[a[i]] = 0;
    }
    return ans;
}

做一个桶sum[]表示一个数有多少个。

部分分代码（60分）

#include
#define ll long long
using namespace std;
int n,k;
int a[1000001];
int dp[1001][1001];
int sum[10001];

inline ll Read() {
    ll ans = 0;
    char Ch = getchar() , Las = ' ';
    while(!isdigit(Ch)) {Las = Ch;Ch = getchar();}
    while(isdigit(Ch)) {ans = (ans << 3) + (ans << 1) + Ch - '0';Ch = getchar();}
    if(Las == '-') ans = -ans;
    return ans;
}

inline void Write(ll x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) Write(x / 10);
    putchar(x % 10 + '0');
}
int dui(int x) {
    x * (x - 1) / 2;
}
int value(int x,int y) {
    int ans = 0;
    memset(sum,0,sizeof(sum));
    int mn = 2e9,mx = 0;
    for(int i = x;i <= y; i++) {
	    sum[a[i]]++;
	    mx = max(mx,a[i]);
	    mn = min(mn,a[i]);
    }
    for(int i = mn;i <= mx; i++) {
	    ans += (sum[a[i]] * (sum[a[i]] - 1) ) / 2;
	    sum[a[i]] = 0;
    }
    return ans;
}

int dfs_dp(int x,int left) {
    if(left == 0) return value(x,n);
    if(left > n - x + 1) return 1e9;
    if(dp[x][left]) return dp[x][left];
    int ans = 2e9;
    for(int i = x;i <= n; i++) {
	    ans = min(ans,value(x,i) + dfs_dp(i + 1,left - 1));
    }
    return dp[x][left] = ans;
}
int flag = 1;
int main() {
    n = Read();
    k = Read();
    for(int i = 1;i <= n; i++) {
	    a[i] = Read();
	    if(a[i]!=a[1]) flag=0;
    }
    if(flag) {
	    ll ans=0;
	    int h = n / k;
	    ans=dui(h + 1) * (n % k) + dui(h) * (k - n % k);
	    Write(ans);
    } else Write(dfs_dp(1,k - 1));
    return 0;
}

全部分

上一个代码超时了。
通过部分分，我们还是可以沿用部分分的思想，进行区间dp，状态转移方程如下：

dp[i][j]=min(dp[i][j],dp[k][j-1]+calc(k+1,i)//calc表示价值

那么对于每一个决策点pl[i],我们不难发现：pl[i - 1] <= pl[i] <= pl[i + 1]
因此我们可以使用决策单调性优化，利用分治思想，暴力求解mid的决策点，从而缩小接下来枚举的范围

void solve(int x,int y,int px,int py) {  //x -> y dp  决策点在px -> py 
    if(x > y) return;
    int mid = x + y >> 1,pl;
    dp[mid][now] = 2e16;
    for(int i = px; i <= min(py,mid - 1); i++) {
	    if(dp[mid][now] > dp[i][now - 1] + calc(i + 1,mid)) {
		    pl = i;  //mid 的决策点（dp转移的位置） 
		    dp[mid][now] = dp[i][now - 1] + calc(i + 1,mid);
	    }
    }
    solve(x,mid - 1,px,pl);
    solve(mid + 1,y,pl,py);
}

求价值也是可以优化的，之前的方法有点慢，我们采用莫队的思想（复杂度很玄，反正就是快了）对其进行优化，其实主要思想还是和桶一样的

ll add(int x) {
    return buc[a[x]]++;
}
ll del(int x) {
    return --buc[a[x]];
}
ll calc(int nl,int nr) {  //i + 1 -> mid 的价值 
    while(r < nr) sum += add(++r);
    while(r > nr) sum -= del(r--);
    while(l > nl) sum += add(--l);
    while(l < nl) sum -= del(l++);
    return sum;
}

AC代码

#include
using namespace std;
#define ll long long
const int N = 1e5 + 100;
int m,n;
int a[N],buc[N];
int l = 1,r = 0;
ll sum = 0;  
ll add(int x) {
    return buc[a[x]]++;
}
ll del(int x) {
    return --buc[a[x]];
}
ll calc(int nl,int nr) {  //i + 1 -> mid 的价值 
    while(r < nr) sum += add(++r);
    while(r > nr) sum -= del(r--);
    while(l > nl) sum += add(--l);
    while(l < nl) sum -= del(l++);
    return sum;
}
ll dp[N][30];
int now;
//pl[i - 1] <= pl[i] <= pl[i + 1] 
void solve(int x,int y,int px,int py) {  //x -> y dp  决策点在px -> py 
    if(x > y) return;
    int mid = x + y >> 1,pl;
    dp[mid][now] = 2e16;
    for(int i = px; i <= min(py,mid - 1); i++) {
	    if(dp[mid][now] > dp[i][now - 1] + calc(i + 1,mid)) {
		    pl = i;  //mid 的决策点（dp转移的位置） 
		    dp[mid][now] = dp[i][now - 1] + calc(i + 1,mid);
	    }
    }
    solve(x,mid - 1,px,pl);
    solve(mid + 1,y,pl,py);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) {
	    scanf("%d",&a[i]);
    }
    for(int i = 1; i <= n; i++) {
	    dp[i][1] = calc(1,i);
    }
    for(int k = 2; k <= m; k++) {
	    now = k;
	    solve(1,n,0,n);
    }
    printf("%lld\n",dp[n][m]);
    return 0;
}