BZOJ 1222
很神奇的一个DP题
嗯、、、这种方程我也是第一次见ORZ
f[i][j]表示完成前i个产品的加工，第一台机器用时j时，第二台机器用时的最小值
转移显然：
f[i][j]=min(f[i][j],f[i-1][j-a[i],f[i-1][j]+b[i],f[i-1][j-z[i]]+z[i])
空间可以压维不是问题
然而我感觉理论上来说时间复杂度是会爆炸的
6000*6000*5
怎么看怎么不靠谱、、
然而BZOJ是总时间所以过了？？？
6666
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #include <string> #include <map> #include <cstring> #include <ctime> #include <vector> #define inf 1e9 #define ll long long #define For(i,j,k) for(int i=j;i<=k;i++) #define Dow(i,j,k) for(int i=k;i>=j;i--) using namespace std; inline void read(int &tx){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} tx=x*f; } inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x+'0'); } inline void writeln(ll x){write(x);puts("");} int n,x[10001],y[10001],z[10001],f[100001],ans=1e9,sum; int main() { read(n); For(i,1,n) { read(x[i]);read(y[i]);read(z[i]); if(x[i]==0) x[i]=1e9;if(y[i]==0) y[i]=1e9;if(z[i]==0) z[i]=1e9; sum+=min(x[i],min(y[i],z[i])); } For(i,0,sum) f[i]=1e9; f[0]=0; For(i,1,n) Dow(j,0,sum) { int tmp=1e9; if(j>=x[i]) tmp=min(tmp,f[j-x[i]]); tmp=min(tmp,f[j]+y[i]); if(j>=z[i]) tmp=min(tmp,f[j-z[i]]+z[i]); f[j]=tmp; } For(i,0,sum) ans=min(max(f[i],i),ans); writeln(ans); }update:
果然不出所料。。在洛谷上tle了
然后滚过来优化
因为当我们枚举到第一个位置时，最大只可能是5，而6~30000是没有必要去算的。。
所以根据这个性质，我们可以优化到n*sum/2
原来是1.8e8
显然变成9e7
。。然后就可以过了‘
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #include <string> #include <map> #include <cstring> #include <ctime> #include <vector> #define inf 1e9 #define ll long long #define For(i,j,k) for(int i=j;i<=k;i++) #define Dow(i,j,k) for(int i=k;i>=j;i--) using namespace std; inline void read(int &tx){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} tx=x*f; } inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x+'0'); } inline void writeln(ll x){write(x);puts("");} int n,x[10001],y[10001],z[10001],f[100001],ans=1e9,sum; int main() { read(n); For(i,0,30000) f[i]=1e9; f[0]=0; For(i,1,n) { read(x[i]);read(y[i]);read(z[i]); if(x[i]==0) x[i]=1e9;if(y[i]==0) y[i]=1e9;if(z[i]==0) z[i]=1e9; sum+=min(x[i],min(y[i],z[i])); Dow(j,0,sum) { int tmp=1e9; if(j>=x[i]) tmp=min(tmp,f[j-x[i]]); tmp=min(tmp,f[j]+y[i]); if(j>=z[i]) tmp=min(tmp,f[j-z[i]]+z[i]); f[j]=tmp; } } For(i,0,30000) ans=min(max(f[i],i),ans); writeln(ans); }
