E. Sheep Eat Wolves

本文主要是介绍E. Sheep Eat Wolves，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://codeforces.com/gym/104869/problem/E

赛时队友想贪心，贪不了一点，我想了数学办法每次都送固定的发现送过去就不满足了

赛后补，暴力做O（n4)

至少要几次才能把安全所有羊送到对岸去

考虑最短路,bfs,用数组存下所有状态

dp[N][N][2]第一维是羊的数量，第二维是狼的数量，第三维是从左边到右，还是从右边到左边，

牧羊人在左边，牧羊人在右边

记录的是左岸的动物状态

暴力写，去除一些不合法状态，状态转移就好了

最后完成任务的状态是min(dp[0][?][1]) 最后一次必然把牧羊人在右边

// Problem: E. Sheep Eat Wolves
// Contest: Codeforces - The 2023 ICPC Asia Shenyang Regional Contest (The 2nd Universal Cup. Stage 13: Shenyang)
// URL: https://codeforces.com/gym/104869/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e2+9;
struct node{int x,y,state;
};
int dp[N][N][2];//x y 0/1   人的位置左岸，右岸
queue<node> Q;
int main(){int X,Y,p,q;cin>>X>>Y>>p>>q;memset(dp,-1,sizeof(dp));//未转移过Q.push({X,Y,0});dp[X][Y][0]=0;//->dp[0][?][1] minwhile(!Q.empty()){auto [x,y,z]=Q.front();Q.pop();if(!z){//->for(int i=0;i<=x;i++){for(int j=0;j<=y;j++){if(i+j>p){continue;}if((y-j)>(x-i)+q && (x-i)>0){//!x 就都到对岸了，合法continue;}if(dp[x-i][y-j][z^1]!=-1){continue;}dp[x-i][y-j][z^1]=dp[x][y][z]+1;Q.push({x-i,y-j,z^1});}}}else{//<-for(int i=0;i<=X-x;i++){for(int j=0;j<=Y-y;j++){if(i+j>p){continue;}if((Y-y-j)>(X-x-i)+q && (X-x-i)>0){continue;}if(dp[x+i][y+j][z^1]!=-1){continue;}dp[x+i][y+j][z^1]=dp[x][y][z]+1;Q.push({x+i,y+j,z^1});}}}}int ans=(1<<30);for(int i=0;i<=Y;i++){if(dp[0][i][1]!=-1){ans=min(ans,dp[0][i][1]);}}if(ans==(1<<30)){cout<<-1<<'\n';}else{cout<<ans<<'\n';	}return 0;
}

这篇关于E. Sheep Eat Wolves的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---