191031-基础测试（dp+搜索剪枝）
T1 农场实习
解析
由于数据范围，所以考虑
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)的算法来求最长不下降子序列
题解
#include<bits/stdc++.h>
using namespace std
;
int read()
{
int f
=1,re
=0;
char ch
;
for(ch
=getchar();!isdigit(ch
)&&ch
!='-';ch
=getchar());
if(ch
=='-')
{
f
=-1;
ch
=getchar();
}
for(;isdigit(ch
);ch
=getchar())
re
=(re
<<3)+(re
<<1)+ch
-'0';
return re
*f
;
}
int n
,a
[1000009],len
,b
[1000009];
int main()
{
scanf("%d",&n
);
for(int i
=0;i
<n
;i
++)
a
[i
]=read();
b
[0]=a
[0];
len
=1;
for(int i
=1;i
<n
;i
++)
{
if(a
[i
]>=b
[len
-1])
b
[len
++]=a
[i
];
else
*upper_bound(b
,b
+len
,a
[i
])=a
[i
];
}
printf("%d",n
-len
);
return 0;
}
T2 运输方案
解析
搜索剪枝 1，可行性剪枝，超重了直接return 2，最优化剪枝，如果当前 maxn+还没选的货物的价值总和 都已经小于或等于ans了，直接return
题解
#include<bits/stdc++.h>
using namespace std
;
int n
;
double a
[34],b
[34],sum
[34],m
,ans
;
bool bj
[34],vis
[34];
void dfs(int cur
,double maxn
,double wei
)
{
if(wei
>m
) return;
if(maxn
+sum
[cur
]<=ans
)
return;
if(cur
==n
+1)
{
if(ans
<maxn
)
{
ans
=maxn
;
for(int i
=1;i
<=n
;i
++)
bj
[i
]=vis
[i
];
}
return;
}
vis
[cur
]=1;
dfs(cur
+1,maxn
+b
[cur
],wei
+a
[cur
]);
vis
[cur
]=0;
dfs(cur
+1,maxn
,wei
);
return;
}
int main()
{
scanf("%lf%d",&m
,&n
);
for(int i
=1;i
<=n
;i
++)
scanf("%lf%lf",&a
[i
],&b
[i
]);
for(int i
=n
;i
>=1;i
--)
sum
[i
]=sum
[i
+1]+b
[i
];
dfs(1,0,0);
printf("%d\n",int(ans
));
if(int(ans
)==0) return 0;
for(int i
=1;i
<=n
;i
++)
if(bj
[i
]) printf("%d ",i
);
return 0;
}
T3 最佳调度问题
解析
搜索剪枝 1，按任务的时间大小降序排序，这样可以快速去掉无用分支 2，最优化剪枝，如果当前要花的时间，已经超过ans了，直接continue
解析
#include<bits/stdc++.h>
using namespace std
;
int used
[100],a
[100],ans
,n
,p
;
bool comp(const int &a
,const int &b
)
{
return a
>b
;
}
void dfs(int cur
,int time
)
{
if(time
>=ans
)
return;
if(cur
==n
+1)
{
ans
=min(time
,ans
);
return;
}
for(int i
=1;i
<=p
;i
++)
{
if(used
[i
]+a
[cur
]>=ans
) continue;
used
[i
]+=a
[cur
];
dfs(cur
+1,max(time
,used
[i
]));
used
[i
]-=a
[cur
];
}
}
int main()
{
scanf("%d%d",&n
,&p
);
for(int i
=1;i
<=n
;i
++)
scanf("%d",&a
[i
]);
sort(a
+1,a
+n
+1,comp
);
ans
=1e8;
dfs(1,0);
printf("%d",ans
);
return 0;
}
