D题就是个搜索居然没有发现
题目大意:先输入一个数n,在输入n个数由0 1构成,从1到0的价值是它们下表差的绝对值,问将所有的1移动到0的最小价值总和是多少(1不能移动到前一个1移走的位置)。
题解:将输入的0和1分别用两个向量存它们的下标
贪心1向量中只能从对应0向量位置向右走深搜
先走到底记录下价值,然后回溯取最小值输出即可
#include <bits/stdc++.h> using namespace std; using ll = long long ; vector<ll>a,b; ///a 0 ///b 1 ll n,_ret,vis[5005][5005],ret[5005][5005],vid,x; ll dfs(int x,int y){ if(y == b.size())return 0; if(x == a.size())return 1e12; ll &_ret=ret[x][y]; if(vis[x][y] == vid) return _ret; vis[x][y]=vid; return _ret=min(dfs(x+1,y+1)+abs(a[x]-b[y]),dfs(x+1,y)); } int main() { ios::sync_with_stdio(false); cin>>n; for(int i=0;i<n;i++){ cin>>x; if(x)b.push_back(i); else a.push_back(i); } vid++; cout<<dfs(0,0); }