20230311模拟赛（jnxxhzz）-JZTXT

T1.团建游戏I

dp，略

T2.团建游戏II

每一次加括号->把一些运算去反

在+后加括号是没有用的，所以每一次只用在-后加

考虑重叠的括号：最多是两层，第三层相当于一层了

对于每一个位置，我们可以用dp记录从这个数字的后面一位往前看有多少个单独的"("

也就是说，对于数字16，我们从"||"向前看: 3 - ( 5 + 5 - 16 ) || + 3

这样就可以写出转移的式子了

$dp_{i,j}$ 编辑表示第i个数字时，前面有多少个没有")"的"("时，前i个的值，j=0/1/2

1* i前面是"-"，那么i可以自己加括号,而在自己加括号是，仍然是-a[i]

$dp_{i,0}=\left\{\begin{matrix} dp_{i-1,1}+a_i \\ dp_{i-1,0}-a_i \\ dp_{i-1,2}-a_i\end{matrix}\right.$

$dp_{i,1}=\left\{\begin{matrix} dp_{i-1,1}+a_i \\ dp_{i-1,0}-a_i \\ dp_{i-1,2}-a_i \end{matrix}\right.$

$dp_{i,2}=\left\{\begin{matrix} dp_{i-1,1}+a_i\\ dp_{i-1,2}-a_i\\ \end{matrix}\right.$

2* i前面是"+"

$dp_{i,0}=\left\{\begin{matrix} dp_{i-1,0}+a_i\\dp_{i-1,1}-a_i \\ dp_{i-1,2}+a_i \end{matrix}\right.$

$dp_{i,1}=\left\{\begin{matrix} dp_{i-1,1}-a_i \\ dp_{i-1,2}+a_i \end{matrix}\right.$

$dp_{i,2}=dp_{i-1,2}+a_i$

最后的答案就是 $\max(dp_{n,j})$

考虑初始化： $\left\{\begin{matrix} dp_{0,0}=0 \\ dp_{0,1}=-\infty \\ dp_{0,2}=-\infty \end{matrix}\right.$

防止dp[0][1]和dp[0][2]被用

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=1e5+10;
int n,T;
ll a[maxn],f[maxn],dp[maxn][3],ans=0;
char ch;

int main(){
  scanf("%d",&T);
  while(T--){
      scanf("%d",&n);
      scanf("%lld",&a[1]);
      for(int i=2;i<=n;i++){
        ch=getchar();ch=getchar();
      if(ch=='-') f[i]=-1;
      else f[i]=1;
      ch=getchar();
      scanf("%lld",&a[i]);    
    }
    f[1]=1;
    dp[0][1]=dp[0][2]=-1e18;//不用memset,会超时！！！
    for(int i=1;i<=n;i++){
      if(f[i]==1){
          dp[i][0]=max(dp[i-1][0]+a[i],max(dp[i-1][1]-a[i],dp[i-1][2]-a[i]));
          dp[i][1]=max(dp[i-1][1]-a[i],dp[i-1][2]+a[i]);
          dp[i][2]=dp[i-1][2]+a[i];
      }
      else{
          dp[i][0]=max(dp[i-1][0]-a[i],max(dp[i-1][1]+a[i],dp[i-1][2]-a[i]));
          dp[i][1]=max(dp[i-1][0]-a[i],max(dp[i-1][1]+a[i],dp[i-1][2]-a[i]));
          dp[i][2]=max(dp[i-1][1]+a[i],dp[i-1][2]-a[i]);
      }
    }
    ans=max(dp[n][0],max(dp[n][1],dp[n][2]));
    printf("%lld\n",ans);
  }
  return 0;
}

T3.团建游戏III

分析发现：

1.在最短距离中，不可能走回头路，所以左右移动距离未|tx|

2.不遇到障碍物不转弯，贴着边缘走路径最短

所以对于每一个障碍物，我们只需要知道它的上、下、左边界

先按照横坐标排序

可以朴素地建图，再跑最短路（考场做法），但只有80分，会TLE

对于每一个走出来的点，它只有可能在遇到障碍时往上或往下

又可以用dp来解决，dp[i][0]表示第i个障碍走上面的距离，dp[i][1]表示走下面

再用线段树维护，找到这个点从哪里来即可

也可以用set暴力，用扫描线的思想完成

代码

#include <bits/stdc++.h>
using namespace std;
#define mid (l+r)/2
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define lb(x) lower_bound(b+1,b+len+1,x)-b
#define int long long

const int maxn=1e6+10;
int n,tx,tr[maxn*4],dp[maxn][2],b[maxn*2],m,t;
struct node{
  int a,b,c,d;
  bool operator < (const node &rhs) const{
    return a<rhs.a;
  }
}a[maxn];

void add(int l,int r,int rt,int lx,int rx,int x){
  if(lx<=l&&rx>=r){tr[rt]=x;return;}
  if(lx<=mid) add(lson,lx,rx,x);
  if(rx>mid) add(rson,lx,rx,x);
}

void query(int l,int r,int rt,int x){
  t=max(t,tr[rt]);
  if(l==r) return ;
  if(x<=mid) query(lson,x);
  else query(rson,x); 
}

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;
}

signed main(){
  n=read();tx=read();
  for(int i=1;i<=n;i++){
      a[i].a=read();a[i].b=read();a[i].c=read();a[i].d=read();
      if(a[i].a>a[i].c) swap(a[i].a,a[i].c);
      if(a[i].b>a[i].d) swap(a[i].b,a[i].d);
      b[i]=a[i].b,b[i+n]=a[i].d;
  }
  m=n*2+1;b[m]=0;
  sort(b+1,b+m+1);
  a[++n]=(node){tx,0,tx,0};
  sort(a+1,a+n+1);
  int len=unique(b+1,b+m+1)-b-1;
  for(int i=1;i<=n;i++){
      t=0;query(1,n,1,lb(a[i].b));
      dp[i][0]=min(dp[t][0]+abs(a[t].b-a[i].b),dp[t][1]+abs(a[t].d-a[i].b));
      t=0;query(1,n,1,lb(a[i].d));
      dp[i][1]=min(dp[t][1]+abs(a[t].d-a[i].d),dp[t][0]+abs(a[t].b-a[i].d));
      add(1,n,1,lb(a[i].b),lb(a[i].d),i);
  }
  printf("%lld\n",dp[n][0]+tx);
  return 0;
}

总结

1.涉及到从前面一个状态转移的都可以考虑用dp，如T3中的dp

2.dp的推导过程中，明确表示内容，如T2中记录的是第i个数字后的括号数