[JSOI] 快递服务 & [SHOI] 书柜的尺寸 优化dp

[JSOI2010]快递服务

朴素思想 ： $f(i,a,b,c)$ 表示前 $i$ 个订单，三个快递员分别在 $a,b,c$

那么可得：

1. $f(i+1,pos[i+1],b,c)=min(f[i][a][b][c]+w[a][pos[i+1]])$
2. $f(i+1,a,pos[i+1],c)=min(f[i][a][b][c]+w[b][pos[i+1]])$
3. $f(i+1,a,b,pos[i+1])=min(f[i][a][b][c]+w[c][pos[i+1]])$

超空间超时间

由于三个快递员之中肯定有一个快递员在上一个订单的位置，我们可以只记录两个不在订单位置的快递员

当前三个快递员：$x,y,pos[i]$

1. $f(i+1,x,y)=min(f[i][x][y]+w[pos[i]][pos[i+1]])$ ($pos[i]\to pos[i+1]$)
2. $f(i+1,x,pos[i])=min(f[i][x][y]+w[y][pos[i+1]])$ ($y\to pos[i+1]$)
3. $f(i+1,y,pos[i])=min(f[i][x][y]+w[x][pos[i+1]])$ ($x\to pos[i+1]$)

由于 $i$ 这一维有关，可用滚动数组优化，注意滚动完后重新初始化过期数据

#include <iostream>
#include <cstring>
using namespace std;
const int inf=1e9+7;
int n,m,w[205][205],p[1005],f[2][205][205];
int main()
{
cin>>m;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
cin>>w[i][j];
}
}
while(cin>>p[++n]);
n--;
memset(f,0x3f,sizeof(f));
f[0][2][3]=0; p[0]=1;
for(int i=0;i<n;i++)
{
for(int a=1;a<=m;a++)
{
for(int b=1;b<=m;b++)
{
if(a==b or a==p[i] or b==p[i]) continue;
f[i+1&1][p[i]][b] = min(f[i+1&1][p[i]][b], f[i&1][a][b] + w[a][p[i+1]]);
f[i+1&1][a][p[i]] = min(f[i+1&1][a][p[i]], f[i&1][a][b] + w[b][p[i+1]]);
f[i+1&1][a][b] = min(f[i+1&1][a][b], f[i&1][a][b] + w[p[i]][p[i+1]]);
}
}
memset(f[i&1],0x3f,sizeof(f[i&1]));
}
int ans = inf;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
if(i==j || j==p[n] || i==p[n]) continue;
ans=min(ans,f[n&1][i][j]);
}
}
cout<<ans;
return 0;
}

[SHOI2007]书柜的尺寸

• 朴素思想：$f(i,w_1,w_2,w_3,h_1,h_2,h_3)$ 分别表示前 $i$ 本书，第一层宽度为 $w_1$，第二层宽度为 $w_2$，第三层宽度为 $w_3$，第一层最高高度为 $h_1$，第二层最高高度为 $h_2$，第三层最高高度为 $h_3$ 的最小面积

• 如果我们已知 $w_1,w_2$ ，那么剩下书的宽度之和即为 $w_3$ ，可以省去这一维

• 由于最高的书一定是最高的，我们不妨将它放在第三层，那么 $h_3$ 也可以省去

• 我们可以按照 $h$ 从大到小排序（不妨设第一本放在第三层），那么第一本放进第一层 或 第二层的书就需要加上其高度，即判断 $w_1,w_2$ 是否为 0 就可以知道这一本书是不是这一层的第一本，因此 $h_1,h_2$ 可以合并成一维 $h_{12}$

• 最终优化为 $f(i,w_1,w_2,h_{12})$

这样还是不够优秀，我们考虑令 $f(i,w_1,w_2)$ 表示前两层的最小高度，那么就可以省去 $h_{12}$

转移方程为：

//按 h 排序后，第一本书在第三层
f[1][0][0] = a[1].h;
for(int i=2;i<=n;i++)
{
for(int w1=0;w1<=sum[i];w1++)
{
for(int w2=0;w2<=sum[i];w2++)
{
f[i][w1][w2] = min(f[i][w1][w2],f[i-1][w1][w2]);
if(w1==0)
f[i][w1+a[i].w][w2] = min(f[i][w1+a[i].w][w2], f[i-1][w1][w2]+a[i].h);
else
f[i][w1+a[i].w][w2] = min(f[i][w1+a[i].w][w2], f[i-1][w1][w2]);
if(w2==0)
f[i][w1][w2+a[i].w] = min(f[i][w1][w2+a[i].w], f[i-1][w1][w2]+a[i].h);
else
f[i][w1][w2+a[i].w] = min(f[i][w1][w2+a[i].w], f[i-1][w1][w2]);
}
}

最终求答案：

for(int w1=1;w1<sum[n];w1++)
{
for(int w2=1;w2<sum[n];w2++)
{
if(f[n][w1][w2]==inf) continue;
ans=min(ans,max3(w1,w2,sum[n]-w1-w2)*f[n][w1][w2]);
}
}

我们将 $i$ 这一维滚动数组优化，记得滚动后的初始化

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
#define max3(a,b,c) max(max(a,b),c)
using namespace std;
int n, inf, sum[75], f[2][2105][2105];
struct Node{
int h,w;
}a[75];
bool cmp(Node x,Node y) {return x.h>y.h;}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].h>>a[i].w;
sum[i]=sum[i-1]+a[i].w;
}
sort(a+1,a+n+1,cmp);
memset(f,0x3f,sizeof(f));
inf = f[0][0][0];
f[1][0][0] = a[1].h;
for(int i=2;i<=n;i++)
{
for(int w1=0;w1<=sum[i];w1++)
{
for(int w2=0;w2<=sum[i];w2++)
{
f[i&1][w1][w2] = min(f[i&1][w1][w2],f[i-1&1][w1][w2]);
if(w1==0)
f[i&1][w1+a[i].w][w2] = min(f[i&1][w1+a[i].w][w2], f[i-1&1][w1][w2]+a[i].h);
else
f[i&1][w1+a[i].w][w2] = min(f[i&1][w1+a[i].w][w2], f[i-1&1][w1][w2]);
if(w2==0)
f[i&1][w1][w2+a[i].w] = min(f[i&1][w1][w2+a[i].w], f[i-1&1][w1][w2]+a[i].h);
else
f[i&1][w1][w2+a[i].w] = min(f[i&1][w1][w2+a[i].w], f[i-1&1][w1][w2]);
}
}
memset(f[i-1&1],0x3f,sizeof(f[i-1&1]));
}
int ans=1e18+5;
for(int w1=1;w1<sum[n];w1++)
{
for(int w2=1;w2<sum[n];w2++)
{
if(f[n&1][w1][w2]==inf) continue;
ans=min(ans,max3(w1,w2,sum[n]-w1-w2)*f[n&1][w1][w2]);
}
}
cout<<ans;
return 0;
}

最后

以上就是忐忑板凳最近收集整理的关于[JSOI] 快递服务 & [SHOI] 书柜的尺寸 优化dp的全部内容，更多相关[JSOI]内容请搜索靠谱客的其他文章。