网站建设与管理专业好吗,网络推广seo培训班,北京专业的做网站,义乌互联网公司文章目录题目描述样例输入样例输出解析代码题目描述
给你一个数列#xff0c;分成m段#xff0c;每段的价值为相同数对的对数 求最小价值和
样例输入 10 2 1 2 1 2 1 2 1 2 1 2 样例输出 8 解析
容易想到区间dp 定义dp[i][j]:把前i个数分成j段的最小价值 那么枚举最后一段…
文章目录题目描述样例输入样例输出解析代码题目描述
给你一个数列分成m段每段的价值为相同数对的对数 求最小价值和
样例输入 10 2 1 2 1 2 1 2 1 2 1 2 样例输出 8 解析
容易想到区间dp 定义dp[i][j]:把前i个数分成j段的最小价值 那么枚举最后一段断点的位置转移就是 dp[i][j]min(dp[i][j],dp[k][j-1]calc(k1,i) (1ki) 不难发现本题是符合决策单调性的 就可以利用这个进行优化啦 使用分治思路
还有一个问题是关于calc的计算 可以使用一个类似于简化的莫队的思路维护两个指针即可 这样就完事啦
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N1e5100;
int m,n;
int a[N],buc[N];
int l1,r0;
ll sum0;
ll add(int x){return buc[a[x]];}
ll del(int x){return --buc[a[x]];}
ll calc(int nl,int nr){while(rnr) sumadd(r);while(rnr) sum-del(r--);while(lnl) sumadd(--l);while(lnl) sum-del(l);return sum;
}
ll dp[N][30];
int now;
void solve(int x,int y,int px,int py){if(xy) return;int midxy1,pl;
// printf(x%d y%d px%d py%d\n,x,y,px,py);dp[mid][now]2e16;for(int ipx;imin(py,mid-1);i){if(dp[mid][now]dp[i][now-1]calc(i1,mid)){pli;dp[mid][now]dp[i][now-1]calc(i1,mid);
// printf(mid%d k%d pl%d dp%d\n,mid,now,pl,dp[mid][now]);}}
// printf(x%d y%d px%d py%d mid%d dp%lld\n,x,y,px,py,mid,dp[mid][now]);solve(x,mid-1,px,pl);solve(mid1,y,pl,py);
}
int main(){
// freopen(dp.in,r,stdin);
// freopen(dp.out,w,stdout);scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,a[i]);}for(int i1;in;i){dp[i][1]calc(1,i);
// printf(i%d k1 dp%lld\n,i,dp[i][1]);}for(int k2;km;k){nowk;solve(1,n,0,n);//for(int i1;in;i) printf(i%d k%d dp%lld\n,i,k,dp[i][k]);}printf(%lld\n,dp[n][m]);
}
/*
10 2
1 2 1 2 1 2 1 2 1 25 2
1 1 1 1 1
*/
