CF1525D 与 对 CF1525D 拓展题目的探究
题目链接:https://codeforces.com/contest/1525/problem/D
类似题目:
① Wannalfy 挑战赛7 Masha与老鼠:https://ac.nowcoder.com/acm/problem/14847
② UOJ【UER #8】雪灾与外卖:https://uoj.ac/problem/455
题目大意
有 n 个坐标 (1\to n) ,a[i] = 1 时表示该位置是老鼠,a[i]=0 时表示该位置是鼠洞。每只老鼠必须匹配一个鼠洞,并且代价是 |i-j| 。保证鼠洞的数目不少于老鼠的数目,求最小代价。
方法1:DP
复杂度 n^2
设 dp[i][j] 表示前 i 个老鼠匹配前 j 个鼠洞的最小代价。(先将老鼠和鼠洞的坐标分离)
(考场上要是有分离的意识,然后想到 dp 就好了。。。)
显然如果老鼠 i 和老鼠 j ,鼠洞 x ,鼠洞 y ,且 i<j ,x<y ,那么肯定是 i 匹配 x ,j 匹配 y 最优。
dp[0][u]=0
转移方程:
①:dp[i][j]=min(dp[i][j],dp[i-1][j-1]+abs(a[i]-b[j]))
表示第 i 只鼠和第 j 只洞匹配,代价是坐标差。
②:dp[i][j]=min(dp[i][j],dp[i][j-1])
表示已经匹配了i只老鼠,跳过第 j 只鼠洞的代价。
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int a[N],t1,dp[N][N],b[N],t2,n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
int x;
scanf("%d",&x);
if(x) a[++t1]=i;
else b[++t2]=i;
}
memset(dp,0x3f,sizeof dp);
memset(dp[0],0,sizeof dp[0]);
for(int i=1;i<=t1;++i){
for(int j=1;j<=t2;++j){
dp[i][j]=std::min(dp[i][j],dp[i-1][j-1]+abs(a[i]-b[j]));
dp[i][j]=std::min(dp[i][j],dp[i][j-1]);
}
}
printf("%d\n",dp[t1][t2]);
return 0;
}
方法2:DP
复杂度 n^2
不分离。
设 dp[i][j] 表示前 i 个坐标,老鼠的数量 – 鼠洞的数量 为 j 时的最小代价。
然后通过拆绝对值进行 dp
由于存在 j<0 的情况,所以我们在实现中给所有 j 加一个偏移量 n 。
#include<bits/stdc++.h>
const int N = 5010;
int n,f[N][N<<1],a[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
memset(f,0x3f,sizeof f);
f[0][n]=0;
for(int i=1;i<=n;++i){
for(int j=0;j<=n<<1;++j){
if(a[i]){
if(j>=1){
if(j<=n)
f[i][j]=f[i-1][j-1]+i;
else
f[i][j]=f[i-1][j-1]-i;
}
}
else{
if(j<n)
f[i][j]=f[i-1][j+1]-i;
else
f[i][j]=f[i-1][j+1]+i;
if(j==n)
f[i][j]=std::min(f[i][j],f[i-1][j]);
}
}
}
printf("%d\n",f[n][n]);
return 0;
}
方法3:方法二的优化 ( O(n) )
可以发现方法二的 DP 有且仅有 j=0 时需要决策,其他位置都只是一个位移(从 j+1 或者 j-1 转移)
再整体加一个值( i )。
可以用两个栈(分为 j<0 和 j>0 来模拟这个转移的过程,j=0 单独计算,然后通过打标记来计算)
#include<bits/stdc++.h>
const int N = 5010;
int n,f[N][N<<1],a[N];
std::stack<int> L,R;
int covL,covR;
int zero = 0 ;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i){
if(a[i]){
covL+=i;
R.push(zero-covR);
covR-=i;
if(!L.empty())zero = L.top()+covL , L.pop();
else zero=1e9;
}
else{
covR+=i;
if(zero!=1e9)
L.push(zero-covL);
covL-=i;
if(!R.empty())
zero=std::min(zero,R.top()+covR),R.pop();
}
}
printf("%d\n",zero);
return 0;
}
方法4:反悔型贪心
复杂度 O(nlogn)
开一个两个小根堆 H0,H1 。
H1 装 多余或者可能反悔的鼠洞的坐标以及代价
H0 装可能反悔的老鼠的代价
H1 装鼠洞,供老鼠进行反悔
H0 装老鼠,供鼠洞进行返回
什么是反悔,就是先选取老鼠 i 与鼠洞 j 进行匹配,代价为 w_1=abs(i-j) ,然后遇到了一个鼠洞 k ,现实是鼠洞 k 与 老鼠 i 匹配更好,但是我们已经贪心的将 i 和 j 匹配了,怎么办?
通过反悔型贪心,撤销过去的贪心操作。我们观察 w_2=k-i-w_1
w_2 表示将 k 和 i 进行匹配,撤销过去的操作的代价。
总代价 w_1+w_2=k-i ,就把第一次不合理的贪心撤销了。
然后具体题目具体分析,可以思考一下为什么要使用小根堆?
#include<bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
const int N = 2e6 + 10;
int n,m;
priority_queue<ll,vector<ll>,greater<ll> > H0,H1;
ll ans = 0 ;
int a[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i){
if(a[i]){
ll w = 1e15; // 如果暂时没有,就假设有一个代价为 1e15 的鼠洞可供选择
// 因为撤销这个操作(反悔)的收益太大了(1e15)。
// 所以这个选择在鼠洞多了以后必然会被撤销
if(!H1.empty()){
ll x = H1.top() ;H1.pop(); //取出可反悔(或者多余的)鼠洞
w = i+x;//计算代价
}
ans += w;
H0.push(-i-w);//添加可供后续反悔的操作
}
else{
if(!H0.empty()&&i+H0.top()<0){ //验证返回了是不是会使总代价减少?
ll w = i + H0.top() ; H0.pop();
ans += w ;
H1.push(-i-w);
}
else{
H1.push(-i);//否则装入H1
}
}
}
printf("%lld",ans);
return 0;
}
0 条评论