T1.团建游戏I
dp,略
T2.团建游戏II
每一次加括号->把一些运算去反
在+后加括号是没有用的,所以每一次只用在-后加
考虑重叠的括号:最多是两层,第三层相当于一层了
对于每一个位置,我们可以用dp记录从这个数字的后面一位往前看有多少个单独的"("
也就是说,对于数字16,我们从"||"向前看: 3 - ( 5 + 5 - 16 ) || + 3
这样就可以写出转移的式子了
编辑表示第i个数字时,前面有多少个没有")"的"("时,前i个的值,j=0/1/2
1* i前面是"-",那么i可以自己加括号,而在自己加括号是,仍然是-a[i]
2* i前面是"+"
最后的答案就是
考虑初始化:
防止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个数字后的括号数
标签:rt,20230311,int,团建,括号,maxn,模拟,jnxxhzz,dp From: https://www.cnblogs.com/hewanying0622/p/17299544.html