20 条题解
-
1
j18tm01 LV 10 @ 2020-05-24 12:18:43
我终于过了QAQ
#include <cstdio> #include <cstring> #define N 21 int na,nb,n,ta[N],tb[N],ka[N],kb[N],tim[N][61][61],dp[N][61][61]; inline int read(){ int 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(); return x*f; } inline int max(int x,int y){return x>y?x:y;} inline int min(int x,int y){return x<y?x:y;} inline void calc(int x){ int t[2][61][61];//0--A,1--B memset(t,0x3f,sizeof(t)); t[1][0][0]=t[0][0][0]=0; for(int i=0;i<=na;++i) for(int j=0;j<=nb;++j){ for(int k=1;k<=i;++k) t[0][i][j]=min(t[0][i][j],t[1][i-k][j]+ta[x]+ka[x]*k*k); for(int k=1;k<=j;++k) t[1][i][j]=min(t[1][i][j],t[0][i][j-k]+tb[x]+kb[x]*k*k); tim[x][i][j]=min(t[0][i][j],t[1][i][j]); } } int main(){ // freopen("a.in","r",stdin); na=read();nb=read();n=read(); for(int i=1;i<=n;++i) ta[i]=read(),tb[i]=read(),ka[i]=read(),kb[i]=read(); for(int i=1;i<=n;++i) calc(i); memset(dp,0x3f,sizeof(dp)); for(int i=0;i<=na;++i) for(int j=0;j<=nb;++j) dp[1][i][j]=tim[1][i][j]; for(int x=2;x<=n;++x) for(int i=0;i<=na;++i) for(int j=0;j<=nb;++j){ for(int ki=0;ki<=i;++ki) for(int kj=0;kj<=j;++kj) dp[x][i][j]=min(dp[x][i][j],max(dp[x-1][i-ki][j-kj],tim[x][ki][kj])); } printf("%d\n",dp[n][na][nb]); return 0; } -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msvar i,j,n,m,p,k,q,x,y,mm,an:longint;
a,b:array[1..200,1..4]of longint;
g:array[0..20,0..200,0..200,1..2]of longint;
f:array[0..100]of longint;
d:array[1..20,0..100]of longint;
function min(o,s:longint):longint;
begin
if os then exit(o)else exit(s);
end;
procedure zhao(l,r:longint);
begin
if l=r then begin an:=l;exit;end;
for i:=1 to m do
f[i]:=-999;
f[0]:=0;
for i:=1 to p do
for j:=0 to m do
d:=-999;
x:=(l+r)div 2;
for i:=1 to p do
for j:=0 to m do
for k:=0 to n do
if g=0 then
f[j]:=max(f[j-k]+d,f[j]);
if f[m]>=n then begin zhao(l,x);exit;end
else begin zhao(x+1,r);exit;end;
end;
begin
read(m,n,p);
for i:=1 to p do
for j:=1 to 4 do
read(a);
fillchar(g,sizeof(g),$7F);
for i:=1 to p do
begin
g:=0;g:=0;
end;
for i:=1 to p do
for j:=0 to m do
for k:=0 to n do
begin
for q:=0 to j-1 do
g:=min(g+a*(j-q)*(j-q)+a,g);
for q:=0 to k-1 do
g:=min(g+a*(k-q)*(k-q)+a,g);
end;
for i:=1 to p do
for j:=0 to m do
for k:=0 to n do
g:=min(g,g);
mm:=99999999;
for i:=1 to p do if mm>g then mm:=g;
zhao(1,mm);
writeln(an);end.
用二分查找法解题
终于过了 AC率啊 -
0
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0mspuppy 就是 神奇 ……
明明 最坏 大概 会运算 2*10^8还多 ， 结果 竟然……DP + 弱弱 的 类似 最优化 剪枝 ……
引用 黑书 上的： 先 枚举 决策 再 枚举 状态，容易 进行“剪枝”。
不过 那 上面 介绍的上下界 估计 看不懂 的说…… 于是 自己 随便找个，结果 貌似还不错 囧…… -
0
做两次DP。
第一次求第i个计算机做x1个a类任务，x2个b类任务所需的组少时间g。
第二次求前i个计算机做x1个a类任务，x2个b类任务所需的组少时间f。
第二次DP的时间复杂度为O(p*na^2*nb^2)，实测会超时，只要加一个小优化。
因为第二次DP是取最大值，并且很容易得到:
当x1'>=x1,x2'>=x2时，g>=g。
所以说如果第i个计算机处理的时间超过了前面i-1个计算机处理的时间，再让第i个计算机做更多的工作只会增加时间，可以剪枝。
这样的话：
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 41ms
├ 测试数据 06：答案正确... 56ms -
0
gnaggnoyil LV 10 @ 2009-04-15 20:24:10
动态规划
参见黑书.
j18tm01
LV 10
@ 2020-05-24 12:18:43
- 1
