スロープ最適化hdu 3480 pku 3709 pku 1180 pku 2180
傾き最適化はDP最適化の一種であり、状態遷移方程式をdp[i]=min or max(dp[k]+w[i,k])と仮定し、そのうちの2つの解k 1,k 2(k 1しかしiに対する単調性はk 1f[ii]の場合、G(k 2,k 3)も>f[ii]の場合、k 3はk 2よりも優れているからである.したがって、このときk 2を削除することができ、削除後G(k 1,k 2)は単調に減少するので、このときのf[ii]をG(k 1,k 2)に挿入すると、前のG(k 1,k 2)はいずれも>=f[ii]となり、このときk 2はk 1よりも優れ、後ろのf[ii]はいずれもk 1よりも優れているので、挿入点のその位置で最適なkkがわかる.具体的な実装は両端とも出られるキューで完了する.各ポイントが1回ずつキューを出すので,時間複雑度はO(n)である.以下、hdu 3480で詳細に説明する.
hdu 3480は、大きな集合をm個の小さな集合に分ける、各集合の最大元素を最小元素二乗と最小とする.四角形不等式も使用できます.並べ替え後、状態遷移方程式はdp[i][j]=min(dp[k][j-1]+(a[i]-a[k+1])^2)となり、k 1
pku 3709は、n個の数を含むシーケンスをいくつかに分けて、少なくともk個の数を含むいくつかの小さなシーケンスに分け、各小さなシーケンスの数がこの小さなシーケンスの最小になり、各数が変化した場合と最小の場合が求められる.
pku1180
傾き最適化と四角形不等式の違いは、四角形不等式がk続単調を満たすことであり、傾きは最適値をとるk単調を保証するだけである.
hdu 3480は、大きな集合をm個の小さな集合に分ける、各集合の最大元素を最小元素二乗と最小とする.四角形不等式も使用できます.並べ替え後、状態遷移方程式はdp[i][j]=min(dp[k][j-1]+(a[i]-a[k+1])^2)となり、k 1
#include<iostream>
#include<algorithm>
using namespace std;
int dp[10010][5010],a[10010],q[10010];
int main()
{
int n,m,i,j,k1,k2,k3,x1,y1,x2,y2,x3,y3,t,test=1,head,tail;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)scanf("%d",&a[i]);
sort(a,a+n);
for(i=0;i<n;i++)
dp[i][1]=(a[i]-a[0])*(a[i]-a[0]);
for(j=2;j<=m;j++)
{
head=0,tail=0;q[tail++]=j-2;
for(i=j-1;i<n;i++)
{
while(head+1<tail)
{
k1=q[head],k2=q[head+1];
if(dp[k2][j-1]-dp[k1][j-1]+a[k2+1]*a[k2+1]-a[k1+1]*a[k1+1]<2*a[i]*(a[k2+1]-a[k1+1]))
head++;
else break;
}
k1=q[head];
dp[i][j]=dp[k1][j-1]+(a[i]-a[k1+1])*(a[i]-a[k1+1]);
while(head+1<tail&&i!=n-1)
{
k1=q[tail-2],k2=q[tail-1],k3=i;
x1=a[k1+1],x2=a[k2+1],x3=a[k3+1];
y1=dp[k1][j-1]+a[k1+1]*a[k1+1];
y2=dp[k2][j-1]+a[k2+1]*a[k2+1];
y3=dp[k3][j-1]+a[k3+1]*a[k3+1];
if((y3-y2)*(x2-x1)<=(y2-y1)*(x3-x2))
tail--;
else
break;
}
q[tail++]=i;
}
}
printf("Case %d: %d/n",test++,dp[n-1][m]);
}
return 0;
} pku 3709は、n個の数を含むシーケンスをいくつかに分けて、少なくともk個の数を含むいくつかの小さなシーケンスに分け、各小さなシーケンスの数がこの小さなシーケンスの最小になり、各数が変化した場合と最小の場合が求められる.
#include<iostream>
using namespace std;
__int64 sum[110000],dp[110000],q[110000];
int main()
{
__int64 n,f,i,j,k,head,tail,k1,k2,k3;
while(scanf("%I64d%I64d",&n,&f)!=EOF)
{
sum[0]=0;
for(i=1;i<=n;i++)
{
scanf("%I64d",&j);
sum[i]=sum[i-1]+j;
}
head=tail=0;
q[tail++]=0;
for(i=f;i<=n;i++)
{
while(head+1<tail)
{
k1=q[head],k2=q[head+1];
if((sum[i]-sum[k1])*(i-k2)<=(sum[i]-sum[k2])*(i-k1))
head++;
else
break;
}
k=q[head];
dp[i]=1000*(sum[i]-sum[k])/(i-k);
while(head+1<tail)
{
k1=q[tail-2],k2=q[tail-1],k3=i-f+1;
if((sum[k2]-sum[k1])*(k3-k2)>=(sum[k3]-sum[k2])*(k2-k1))
tail--;
else
break;
}
q[tail++]=i-f+1;
}
for(k=0,i=f;i<=n;i++)
if(dp[i]>k)
k=dp[i];
printf("%I64d/n",k);
}
return 0;
}pku1180
// ，
// ， ，
// + S+
// Fi， Fi*
// :f[i]=min(f[k]+(ST[i]-ST[k]+S)*(F[n]-F[k]));
#include<iostream>//#include "stdafx.h"
using namespace std;//#define int L//#define __int64 LL
const __int64 maxn=11000;
__int64 n,S,f[maxn],q[maxn],T[maxn],F[maxn],ST[maxn],SF[maxn];
__int64 C(__int64 k,__int64 i)
{
return f[k]+(ST[i]-ST[k]+S)*(SF[n]-SF[k]);
}
int main()
{
__int64 i,head,tail,k1,k2,k3,x1,x2,x3,y1,y2,y3;
while(scanf("%I64d%I64d",&n,&S)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%I64d%I64d",&T[i],&F[i]);
ST[0]=SF[0]=0;
for(i=1;i<=n;i++)
{
ST[i]=ST[i-1]+T[i];
SF[i]=SF[i-1]+F[i];
}
head=tail=0;
q[tail++]=0;
f[0]=0;
for(i=1;i<=n;i++)
{
while(head+1<tail)
{
k1=q[head],k2=q[head+1];
if(C(k2,i)<=C(k1,i))
head++;
else
break;
}
f[i]=C(q[head],i);
while(head+1<tail)
{
k1=q[tail-2],k2=q[tail-1],k3=i;
x1=SF[k1],x2=SF[k2],x3=SF[k3];
y1=f[k1]-ST[k1]*(SF[n]-SF[k1]);
y2=f[k2]-ST[k2]*(SF[n]-SF[k2]);
y3=f[k3]-ST[k3]*(SF[n]-SF[k3]);
if((y2-y1)*(x3-x2)>=(y3-y2)*(x2-x1))
tail--;
else
break;
}
q[tail++]=i;
}
printf("%I64d/n",f[n]);
}
return 0;
}傾き最適化と四角形不等式の違いは、四角形不等式がk続単調を満たすことであり、傾きは最適値をとるk単調を保証するだけである.