P1220 关路灯
很典的一道题，但是以前居然不知道。
数据范围很小，可以直接搜索通过，加一些奇奇怪怪的贪心策略和剪枝即可和正解差不多速度通过。
\(Code_violent\)
ll ans=9e18;
int n,st,loc[51],p[51];
void dfs(int x,ll t,ll res,ll P,int l,int r){
res+=t*p[x];
P-=p[x];
if(res+P*t>=ans)return;
if(!l&&r==n+1)return ans=res,void();
if(l)dfs(l,t+loc[x]-loc[l],res,P,l-1,r);
if(r<=n)dfs(r,t+loc[r]-loc[x],res,P,l,r+1);
}
int main(){
n=read(),st=read();
ll P=0;
for(int i=1;i<=n;i++)
loc[i]=read(),P+=p[i]=read();
dfs(st,0,0,P,st-1,st+1);
cout<<ans<<endl;
return 0;
}
然后基于上述搜索用到的贪心：每次只可能向左或向右拓展一格，证明显然。
所以不难推出转移，因为要记在左边还是右边，所以我们开三维 \(f_{0/1,l,r}\) 表示关掉 \(l,r\) 的灯之后留在左/右处时消耗的最小电量。然后转移非常很好推，用个前缀和优化可以做到 \(O(n^2)\)。
\(Code\)
int n,st,loc[52];
ll sum[52],f[2][52][52];//0 is left
inline ll cal(int l,int r){return sum[l-1]+sum[n]-sum[r];}
int main(){
n=read(),st=read();
for(int i=1;i<=n;i++)
loc[i]=read(),sum[i]=sum[i-1]+read();
memset(f,0x3f,sizeof(f));
f[0][st][st]=f[1][st][st]=0;
for(int len=2;len<=n;len++)
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
f[0][i][j]=min(f[0][i+1][j]+cal(i+1,j)*(loc[i+1]-loc[i]),f[1][i+1][j]+cal(i+1,j)*(loc[j]-loc[i]));
f[1][i][j]=min(f[0][i][j-1]+cal(i,j-1)*(loc[j]-loc[i]),f[1][i][j-1]+cal(i,j-1)*(loc[j]-loc[j-1]));
}
printf("%lld",min(f[0][1][n],f[1][1][n]));
return 0;
}
P2466 [SDOI2008] Sue 的小球
和上面那道的贪心思路差不多，都是左右扩展是最优的，所以转移方程差不多，要注意的是，这个需要类似于离散化的方式重构数组，然后就和上面那题一样了。不过注意如果像我这样直接整数保留三位要先输出负号，否则会被除法吞掉。
\(Code\)
const int N=1003;
int n,st,loc[N];
ll sum[N],ans,f[2][N][N];
map<int,int>M;
inline ll cal(int l,int r){return sum[l-1]+sum[n]-sum[r];}
int main(){
n=read(),M[st=read()]=0;
for(int i=1;i<=n;i++)loc[i]=read();
for(int i=1;i<=n;i++)ans+=read();
for(int i=1;i<=n;i++)M[loc[i]]+=read();
int be=n=0;
for(auto PI:M){
loc[++n]=PI.first;
if(PI.first==st)be=n;
sum[n]=sum[n-1]+PI.second;
}
memset(f,0x3f,sizeof(f));
f[0][be][be]=f[1][be][be]=0;
for(int len=2;len<=n;len++)
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
f[0][i][j]=min(f[0][i][j],min(f[0][i+1][j]+cal(i+1,j)*(loc[i+1]-loc[i]),f[1][i+1][j]+cal(i+1,j)*(loc[j]-loc[i])));
f[1][i][j]=min(f[1][i][j],min(f[0][i][j-1]+cal(i,j-1)*(loc[j]-loc[i]),f[1][i][j-1]+cal(i,j-1)*(loc[j]-loc[j-1])));
}
ans-=min(f[0][1][n],f[1][1][n]);
if(ans<0)putchar('-'),ans=-ans;
printf("%lld.%03lld",ans/1000,ans%1000);
return 0;
}
P4870 [BalticOI 2009 Day1] 甲虫
和 P2466 那题的 dp 思路有点相似，只不过这题因为 \(m\) 有上限，我们不能保证自己喝掉每一滴露水，这导致如果我们假定喝了全部露水然后跑 dp 的话会导致一些露水的贡献是负数因此不优。发现这道题可以跑 \(O(n^3)\)，所以我们直接枚举喝的露水个数即可。
\(Code\)
const int N=303;
int n,m,loc[N],f[2][N][N],ans;
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)loc[i]=read();loc[++n]=0;
sort(loc+1,loc+1+n);
int st=lower_bound(loc+1,loc+1+n,0)-loc;
for(int maxl=2;maxl<=n;maxl++){
memset(f,0x3f,sizeof(f));
f[0][st][st]=f[1][st][st]=0;
for(int len=2;len<=maxl;len++)
for(int i=1,j=len;j<=n;i++,j++)
f[0][i][j]=min(f[0][i+1][j]+(maxl-len+1)*(loc[i+1]-loc[i]),f[1][i+1][j]+(maxl-len+1)*(loc[j]-loc[i])),
f[1][i][j]=min(f[0][i][j-1]+(maxl-len+1)*(loc[j]-loc[i]),f[1][i][j-1]+(maxl-len+1)*(loc[j]-loc[j-1]));
for(int i=1;i<=n;i++)
ans=max(ans,m*(maxl-1)-min(f[0][i][i+maxl-1],f[1][i][i+maxl-1]));
}
cout<<ans;
return 0;
}
后记
暂时不想写 dp 了，去练习图论了。
2023.11.6 16:18 end