题目

题目

思路

考虑4维 可能也可以理解为5维 的背包

但是好像跑得挺快的

时间复杂度应该是 O ( n ∑ i = 1 n − 1 a i a i + 1 b 2 ) O(n\sum_{i=1}^{n-1} a_ia_{i+1}b^2) O(n∑i=1n−1​ai​ai+1​b2)

因为 n = ∑ i = 1 n a i n=\sum_{i=1}^{n} a_i n=∑i=1n​ai​，所以这玩意在随机数据下应该挺快的

同时我们可以把不生产果子的果园打个不使用的tag，在dp转移时跳过该果园。

当然可以直接删掉，下面写的方程就是这样的

设 f i , j , k , l , 1 / 0 f_{i,j,k,l,1/0} fi,j,k,l,1/0​表示已考虑前i个果园，其中第i个果园向一号基地运j吨果子，现在1号基地已开k台机器，2号则开l台机器的最优方案，最后一维为0表示最优方案的运输部分用时，为1表示最优方案的加工部分用时。

现在枚举i,j,k,l，把当前状态转移到前i+1个果园的状态，所以再枚举一个j2表示i+1号果园运j2吨果子去1号基地。

接下来上方程：

f i , j , k , l ⇒ { f i + 1 , j 2 , k , l + c 2 , i + 1 j 2 = = 0 f i + 1 , j 2 , k + c 1 , i + 1 , l j 2 = = a i + 1 f i + 1 , j 2 , k + c 1 , i + 1 , l + c 2 , i + 1 e l s e f_{i,j,k,l}\Rightarrow \begin{cases}f_{i+1,j2,k,l+c_{2,i+1}}&j2==0\\f_{i+1,j2,k+c_{1,i+1},l}&j2==a_{i+1}\\f_{i+1,j2,k+c_{1,i+1},l+c_{2,i+1}}&else\end{cases} fi,j,k,l​⇒⎩⎪⎨⎪⎧​fi+1,j2,k,l+c2,i+1​​fi+1,j2,k+c1,i+1​,l​fi+1,j2,k+c1,i+1​,l+c2,i+1​​​j2==0j2==ai+1​else​

当然上述方程是建立在转移后更优的情况下的。

最后的答案统计非常简单，把 f n , j , k , l f_{n,j,k,l} fn,j,k,l​扫一遍就行
同步于我的nowcoder blogs

code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
inline long long read()
{
	long long ret,c,f=1;
	while (((c=getchar())> '9'||c< '0')&&c!='-');
	if (c=='-') f=-1,ret=0;
	else ret=c-'0';
	while ((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
	return ret*f;
}
long long n,a[100],b[3],c[3][100],d[3][100],u[3][100],f[100][100][100][100][2],ans=3000000000000;
int main()
{
	n=read();
	for (int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	b[1]=read(),b[2]=read();
	for (int i=1;i<=n;i++) c[1][i]=read();
	for (int i=1;i<=n;i++) c[2][i]=read();
	for (int i=1;i<=n;i++) d[1][i]=read();
	for (int i=1;i<=n;i++) d[2][i]=read();
	for (int i=1;i<=n;i++) u[1][i]=read();
	for (int i=1;i<=n;i++) u[2][i]=read();
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<=a[i];j++) for (int k=0;k<=b[1];k++) for (int jk=0;jk<=b[2];jk++) f[i][j][k][jk][0]=f[i][j][k][jk][1]=3000000000000;
	}
	f[0][0][0][0][0]=f[0][0][0][0][1]=0; 
	for (int i=0;i<=n;i++)//枚举果园 
	{
		for (int j=0;j<=a[i];j++)//枚举去1号的个数 
		{
			for (int k=0;k<=b[1];k++)
			{
				for (int jk=0;jk<=b[2];jk++)
				{
					if (a[i+1]==0)
					{
						f[i+1][j][k][jk][0]=f[i][j][k][jk][0];
						f[i+1][j][k][jk][1]=f[i][j][k][jk][1];
						continue;
					}
					for (int kk=0;kk<=a[i+1];kk++)
					{
						long long tmp=max(f[i][j][k][jk][0],max(d[2][i+1]*(a[i+1]-kk),d[1][i+1]*kk))+max(f[i][j][k][jk][1],max(u[2][i+1]*(a[i+1]-kk),u[1][i+1]*kk));
						if (kk==0)
						{
							if (tmp<f[i+1][kk][k][jk+c[2][i+1]][0]+f[i+1][kk][k][jk+c[2][i+1]][1])
							{
								f[i+1][kk][k][jk+c[2][i+1]][0]=max(f[i][j][k][jk][0],max(d[2][i+1]*(a[i+1]-kk),d[1][i+1]*kk));
								f[i+1][kk][k][jk+c[2][i+1]][1]=max(f[i][j][k][jk][1],max(u[2][i+1]*(a[i+1]-kk),u[1][i+1]*kk));
							}
						}
						else if (kk==a[i+1])
						{
							if (tmp<f[i+1][kk][k+c[1][i+1]][jk][0]+f[i+1][kk][k+c[1][i+1]][jk][1])
							{
								f[i+1][kk][k+c[1][i+1]][jk][0]=max(f[i][j][k][jk][0],max(d[2][i+1]*(a[i+1]-kk),d[1][i+1]*kk));
								f[i+1][kk][k+c[1][i+1]][jk][1]=max(f[i][j][k][jk][1],max(u[2][i+1]*(a[i+1]-kk),u[1][i+1]*kk));
							}
						}
						else
						{
							if (tmp<f[i+1][kk][k+c[1][i+1]][jk+c[2][i+1]][0]+f[i+1][kk][k+c[1][i+1]][jk+c[2][i+1]][1])
							{
								f[i+1][kk][k+c[1][i+1]][jk+c[2][i+1]][0]=max(f[i][j][k][jk][0],max(d[2][i+1]*(a[i+1]-kk),d[1][i+1]*kk));
								f[i+1][kk][k+c[1][i+1]][jk+c[2][i+1]][1]=max(f[i][j][k][jk][1],max(u[2][i+1]*(a[i+1]-kk),u[1][i+1]*kk));
							}
						}
					}
				}
			}
		}
	}
	for (int j=0;j<=a[n];j++)
	{
		for (int k=0;k<=b[1];k++)
		{
			for (int jk=0;jk<=b[2];jk++)
			{
				ans=min(ans,f[n][j][k][jk][0]+f[n][j][k][jk][1]);
			}
		}
	}
	cout<<ans;
	return 0;
}