【意思決定単調性分治最適化/四角形不等式最適化】刑務所警備

前言
テンプレートセットでACになりました...
タイトル
guardians.cpp 1S/128M
あなたは刑務所の警備員を最もクレイジーな犯罪者がいる刑務所に派遣する責任を負っています.全部でN室が1行に並び、番号は1~Nから.i番目の牢屋には、C[i]の狂気の犯罪者が収容されている.
すべての犯罪者は警備員が彼/彼女を監視しなければならない.理想的には、警備員に犯罪者を監視させるべきだ.しかし、予算制限のため、G人の警備員を割り当てるしかありません.誰かが逃げる総リスクを最小限に抑えるためには、警備員一人一人がどの犯罪者を監視すべきかを指定する必要があります.もちろん、警備員一人一人を隣の牢屋に割り当てるべきです.i番目の犯罪者が脱出する可能性のあるリスクR[i]は、R[i]=C[i]*が警備監視を監視する犯罪者の数を割り当て、すべての犯罪者のリスクの和を最小限に抑える最適な案を割り当ててください.
1行目:2個の整数NとG(1<=N<=8000、1<=G<=800)2行目:N個の整数を入力し、C[i](1<=C[i]<=10^9を表す.
出力1行目:1個の整数、答えを表す
Sample Input 6 3 11 11 11 24 26 100
Sample Output 299
Explain第1警備監視1~3、第2警備監視4~5、第3警備監視6
ぶんせき
詳細はこの最適化の説明について私はブログを書きます:決定の単調性の分治の最適化
本問題の基本モデルは,パケット+コストの最小化であることが観察された.
DP定義と移行方程式を書くことができます.
dp[i][j]:1~j犯人はi番目の獄長に監督された
最後の獄長iについて,k番目からj番目の犯人が最後のi番目の獄長に監督されると仮定する.
dp[ i ][ j ]=min( dp[ i ][ j ],dp[ i-1 ][ k-1 ]+( s[ j ] - s[ k ] ) * ( j - k + 1 ) ) ;                                                                                                   
s[i]:1~iの接頭辞和
初期化:dp[1][1~n]=INF
次に、「意思決定単調性分治最適化」または「四角形不等式最適化」を直接適用すればよい.詳細はコードを参照
意思決定単調性分治最適化−コード(暴力DPを含む)

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int MAXN=8000,MAXG=800;
#define INF (1LL << 60) 
ll c[MAXN+5],s[MAXN+5],dp[MAXG+5][MAXN+5];
ll n,g;
void DP(ll d,ll i,ll j,ll optl,ll optr)//     
{
	if(i>j)
		return ;
	ll mid=(i+j)/2;
	ll opt=INF,id;
	//        dp opt      id 
	for(int k=optl;k<=min(mid,optr);k++)
	{
		ll cur=dp[d-1][k-1]+(mid-k+1)*(s[mid]-s[k-1]);
		if(cur

四角形不等式最適化-コード

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int MAXN=8000,MAXG=800;
#define INF (1LL<<60) 
ll c[MAXN+5],s[MAXN+5],dp[MAXG+5][MAXN+5];
ll n,g;
void Solve()
{
	for(int i=0;i<=g;i++)
		for(int j=0;j<=n;j++)
			dp[i][j]=INF;
	dp[0][0]=0;
	for(int i=1;i<=g;i++)
	{
		ll opt=0;
		for(int j=i;j<=n;j++)
			for(int k=opt;k<=j;k++)
			{
				ll tmp=1ll*(j-k+1)*(s[j]-s[k-1]);
				if(dp[i-1][k-1]+tmp<=dp[i][j])
					dp[i][j]=dp[i-1][k-1]+tmp,opt=k;
			}
	}
	/*        
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
		{
			w[i][j]=(j-i+1)*(s[j]-s[i-1]);
			//printf("%d %d %lld
",i,j,w[i][j]);
		}
	for(int a=1;a<=n;a++)
		for(int b=a+1;b<=n;b++)
			for(int c=b+1;c<=n;c++)
				for(int d=c+1;d<=n;d++)
					printf("%d %d %d %d %lld %lld
",a,b,c,d,w[a][c]+w[b][d],w[a][d]+w[b][c]);
	*/
	printf("%lld
",dp[g][n]);
}
int main()
{
	scanf("%lld%lld",&n,&g);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&c[i]);
		s[i]=s[i-1]+c[i];
	}
	Solve();
	return 0;
}