P9505 题解
首先我们容易想到直接 \(dp[i][j]\) 表示前 \(i\) 个中选 \(j\) 个的答案最小值,明显把a[i]==0不会更劣
接着由于这种方法明显时间复杂度 \(O(n^3)\)，所以考虑优化。
怎么优化 据题解曰 可以把 \(dp[i][j]\) 状态改为：在选第 \(i\) 个的时候前 \(i\) 个至少选了 \(j\) 个答案最小值。
可以推出下列公式：
\[dp[i][m]=min_{k:1}^{i-1}{\{dp[k][m-1]+val(k,i),dp[k][m]+val(k,i)\}}.
\]
答案很明显就是 $ max_{i=1}^{n}{{ dp[i][k]+val(i,n+1)}} $。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define bi ((j-i-1)/2)
int n,k,dp[3050][110],tmp[3050],a[3050];
inline int val(int i,int j){return a[j]*a[j]+((j-i)*(j-i-1)/2)*max(a[i],a[j]);
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>k;int zp=0;for(int i=1;i<=n;i++){cin>>tmp[i];if(tmp[i]==0) zp=i;}int cnt=0;for(int i=zp;i<=n;i++){a[++cnt]=tmp[i];}for(int i=1;i<zp;i++){a[++cnt]=tmp[i];}// for(int i=1;i<=n;i++) cout<<a[i]<<" ";// cout<<"\n";memset(dp,0x3f,sizeof(dp));dp[1][1]=0;//dp[i][m]表示在激活i的情况下，前i个至少激活m个的答案最小值(实际上只有在m==k才是正确否则是刚好)for(int i=2;i<=n;i++){for(int m=2;m<=min(i,k);m++){for(int j=1;j<i;j++){int ttmp=val(j,i);dp[i][m]=min(dp[i][m],dp[j][m-1]+ttmp);dp[i][m]=min(dp[i][m],dp[j][m]+ttmp);//为什么可以加上一个 $if(m==k)$在第二行前}}}int ans=INT_MAX;for(int i=1;i<=n;i++) ans=min(ans,dp[i][k]+val(i,n+1));cout<<ans;return 0;
}