CF536D Tavas in Kansas（博弈论+dp）

貌似洛谷的题面是没有翻译的

QWQ

大致题面是这个样子，但是可能根据题目本身有不同的地方

完全懵逼的一个题（果然博弈论就是不一样）

首先，我们考虑把题目转化成一个可做的模型。

我们分别从\(s\)和\(t\)跑两边全图最短路，这样，对于每个点，我们就能得到\(dis[i]\)和\(disn[i]\)。

这时候，我们把每个图上的点，看成一个平面上的点\((dis[i],disn[i])\)，那么对于\(Alice\)来说，一次就相当于取若干行，\(Bob\)就是取若干列。然后两个人最大化分数差

不难发现，这个问题，我们可以通过离散化之后，就可以直接dp了

QWQ

（虽然dp部分更难想）

考虑到我们只知道起始状态，所以我们要尝试直接倒着\(dp\)，令\(dp[i][j][0/1]\)表示当前是该\(Alice/Bob\)操作，然后还没有分配的区域是\((i+1,j+1)->(n,m)\)的最大分数差。

或者换种说法，

就是示\(覆盖了[x+1~n] 行，[y+1~m]列，当前取行/列的最大/最小差距\)

QWQ虽然感觉这个dp状态有点诡异

转移的时候，一次转移一行或者一列

对于当前的一个状态\(dp[i][j][0]\)，我们需要\(check\)一下有没有第\(i+1\)i行有没有数（权值），如果没有，那么只能从\(dp[i+1][j][0]\)转移过来（这里可以理解为，如果没有数，那么一定是只能从上一个人那里转移过来），

不然就是\(max(dp[i+1][j][0],dp[i+1][j][1])+val\)（可以和上一次一样，或者单独拿了这个），令一状态也同理

for (int i=hang;i>=0;i--)

    for (int j=line;j>=0;j--)

    {

     //if (i==line && j==line)

     if (i!=hang)

     {

      int now = getnumx(i+1,j+1,line);

      int ss = getsumx(i+1,j+1,line);

      if (!now) dp[i][j][0]=dp[i+1][j][0];

      else dp[i][j][0]=max(dp[i+1][j][0],dp[i+1][j][1])+ss;

  }

  if (j!=line)

  {

   int now = getnumy(j+1,i+1,hang);

      int ss = getsumy(j+1,i+1,hang);

      if (!now) dp[i][j][1]=dp[i][j+1][1];

      else dp[i][j][1]=min(dp[i][j+1][0],dp[i][j+1][1])-ss;

  }

 }

官方题解我也放一下

下面是整个的代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#include<set>

#define mk makr_pair

#define int long long

#define pa pair<long long,long long>

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 2010;

const int maxm = 1e6+1e2;

int point[maxn],nxt[maxm],to[maxm];

int cnt,n,m;

int dis[maxn],vis[maxn];

int sumx[maxn][maxn],sumy[maxn][maxn];

int numx[maxn][maxn],numy[maxn][maxn];

int val[maxm];

int disn[maxn];

int cost[maxn];

int hang,line;

int s,t;

int sum[maxn][maxn];

int num[maxn][maxn];

int dp[maxn][maxn][2];

priority_queue<pa,vector<pa>,greater<pa> > q;

struct Node{

 int x,y;

};

Node a[maxn];

vector<int> vx,vy;

void addedge(int x,int y,int w)

{

 nxt[++cnt]=point[x];

 to[cnt]=y;

 val[cnt]=w;

 point[x]=cnt;

}

void dijkstra(int s)

{

 memset(vis,0,sizeof(vis));

 memset(dis,127/3,sizeof(dis));

 dis[s]=0;

 q.push(make_pair(0,s));

 while (!q.empty())

 {

  int x=q.top().second;

  q.pop();

  if (vis[x]) continue;

  vis[x]=1;

  for (int i=point[x];i;i=nxt[i])

  {

   int p = to[i];

   if (dis[p]>dis[x]+val[i])

   {

    dis[p]=dis[x]+val[i];

    q.push(make_pair(dis[p],p));

   }

  }

 }

}

void dijkstran(int s)

{

 memset(vis,0,sizeof(vis));

 memset(disn,127/3,sizeof(disn));

 disn[s]=0;

 q.push(make_pair(0,s));

 while (!q.empty())

 {

  int x=q.top().second;

  q.pop();

  if (vis[x]) continue;

  vis[x]=1;

  for (int i=point[x];i;i=nxt[i])

  {

   int p = to[i];

   if (disn[p]>disn[x]+val[i])

   {

    disn[p]=disn[x]+val[i];

    q.push(make_pair(disn[p],p));

   }

  }

 }

}

//之所以倒着dp的原因是，因为我们只知道开始局面先手的情况，所以需要倒着来推

int getnumx(int x,int l,int r) {return numx[x][r]-numx[x][l-1];}

int getnumy(int y,int l,int r) {return numy[r][y]-numy[l-1][y];}

int getsumx(int x,int l,int r) {return sumx[x][r]-sumx[x][l-1];}

int getsumy(int y,int l,int r) {return sumy[r][y]-sumy[l-1][y];}

signed main()

{

  n=read(),m=read();

  s=read(),t=read();

  int flag=0;

  for (int i=1;i<=n;i++) cost[i]=read();

  for (int i=1;i<=m;i++)

  {

   int x=read(),y=read(),w=read();

   addedge(x,y,w);

   addedge(y,x,w);

  }

 // flag=read();

  dijkstra(s);

  dijkstran(t);

 // cout<<dis[3]<<" "<<disn[4]<<endl;

  for (int i=1;i<=n;i++) vx.push_back(dis[i]),vy.push_back(disn[i]);

  sort(vx.begin(),vx.end());

  sort(vy.begin(),vy.end());

  int hang = unique(vx.begin(),vx.end())-vx.begin();

  int line = unique(vy.begin(),vy.end())-vy.begin();

  vx.resize(hang);

  vy.resize(line);

  for (int i=1;i<=n;i++)

  {

    int x = lower_bound(vx.begin(),vx.end(),dis[i])-vx.begin()+1;

    int y = lower_bound(vy.begin(),vy.end(),disn[i])-vy.begin()+1;

    num[x][y]++;

    sum[x][y]+=cost[i];

  }

  for (int i=1;i<=hang+1;i++)

    for (int j=1;j<=line+1;j++)

     sumx[i][j]=sumx[i][j-1]+sum[i][j],numx[i][j]=numx[i][j-1]+num[i][j];

  for (int j=1;j<=line+1;j++)

    for (int i=1;i<=hang+1;i++)

     sumy[i][j]=sumy[i-1][j]+sum[i][j],numy[i][j]=numy[i-1][j]+num[i][j];

  //这里具体的dp数组的含义就是这一次是该谁操作，然后剩下没有被占领的是从(i+1,j+1)到(n,m)这个子矩形的分数差

  for (int i=hang;i>=0;i--)

    for (int j=line;j>=0;j--)

    {

     //if (i==line && j==line)

     if (i!=hang)

     {

      int now = getnumx(i+1,j+1,line);

      int ss = getsumx(i+1,j+1,line);

      if (!now) dp[i][j][0]=dp[i+1][j][0];

      else dp[i][j][0]=max(dp[i+1][j][0],dp[i+1][j][1])+ss;

  }

  if (j!=line)

  {

   int now = getnumy(j+1,i+1,hang);

      int ss = getsumy(j+1,i+1,hang);

      if (!now) dp[i][j][1]=dp[i][j+1][1];

      else dp[i][j][1]=min(dp[i][j+1][0],dp[i][j+1][1])-ss;

  }

 }

  if(dp[0][0][0]>0) cout<<"Break a heart"<<"\n";

  if(dp[0][0][0]<0) cout<<"Cry"<<"\n";

  if (dp[0][0][0]==0) cout<<"Flowers"<<"\n";

  return 0;

}

巴特西

CF536D Tavas in Kansas（博弈论+dp）

最新文章

热门文章