[HNOI 2008]おもちゃ箱詰めtoy(dp+スロープ最適化)
2292 ワード
スロープ最適化問題は一般的に決定単調問題である.この問題に対して単調な決定を証明することができる.
sum[i]=sigma(c[k])1<=k<=i,f[i]=sum[i]+i,c=L+1とする.
まず,転移方程式dp[i]=min(dp[j]+(f[i]−f[j]−c)^2)を書くことができる.意思決定j 1 dp[j2]+(f[i]-f[j2]-c)^2<=dp[j1]+(f[i]-f[j1]-c)^2
バンド((dp[j 2]+f[j 2]^2)−(dp[j 1]+f[j 1]^2))/(f[j 2]−f[j 1])<2*(f[i]−c)を得ることができる.
f[i]よりも優れているのは増加するので、t>iの点では、決定j 2は常にj 1よりも優れており、j 1は実際には決定セットから削除することができる.後ろのものは1つのキューでメンテナンスできます.
sum[i]=sigma(c[k])1<=k<=i,f[i]=sum[i]+i,c=L+1とする.
まず,転移方程式dp[i]=min(dp[j]+(f[i]−f[j]−c)^2)を書くことができる.意思決定j 1
バンド((dp[j 2]+f[j 2]^2)−(dp[j 1]+f[j 1]^2))/(f[j 2]−f[j 1])<2*(f[i]−c)を得ることができる.
f[i]よりも優れているのは増加するので、t>iの点では、決定j 2は常にj 1よりも優れており、j 1は実際には決定セットから削除することができる.後ろのものは1つのキューでメンテナンスできます.
<span style="font-size:14px;">#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <string>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int inf = 0x3fffffff;
const int mmax =50010;
LL C[mmax];
LL L,c;
LL sum[mmax],f[mmax],dp[mmax];
LL sqr(LL x)
{
return x*x;
}
double G(int x)
{
return 1.0*f[x]*f[x]+dp[x];
}
double S(int x)
{
return 2.0*f[x];
}
void calc(int i,int j)
{
dp[i]=dp[j]+sqr(f[i]-f[j]-c);
}
int Q[mmax];
int main()
{
int n;
while(cin>>n>>L)
{
c=L+1;
sum[0]=0;
f[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&C[i]);
sum[i]=sum[i-1]+C[i];
f[i]=sum[i]+i;
}
int head=0,tail=-1;
dp[0]=0;
Q[++tail]=0;
for(int i=1;i<=n;i++)
{
while(head<tail)
{
double tmp=1.0*(G(Q[head+1])-G(Q[head]))/(S(Q[head+1])-S(Q[head]));
if(tmp<=f[i]-c)
head++;
else
break;
}
calc(i,Q[head]);
while(head<tail)
{
double tmp1=1.0*(G(Q[tail])-G(Q[tail-1]))/(S(Q[tail])-S(Q[tail-1]));
double tmp2=1.0*(G(i)-G(Q[tail]))/(S(i)-S(Q[tail]));
if(tmp1>=tmp2)
tail--;
else
break;
}
Q[++tail]=i;
}
printf("%lld
",dp[n]);
}
return 0;
}
</span>