Link:

A:

分层图最短路（其实就是最短路转移时多记录一维的数据

#include 
      
       using namespace std;#define X first#define Y secondtypedef double db;typedef long long ll;typedef pair
       
         P;const int MAXN=105;int n,T,dat[MAXN][MAXN];ll d[MAXN][MAXN][3];struct node{
    int x,y,d,w;};int dx[]={
    0,0,1,-1};int dy[]={
    1,-1,0,0};priority_queue
        
          q;bool operator < (node a,node b){
    return a.w>b.w;}int main(){    scanf("%d%d",&n,&T);    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            scanf("%d",&dat[i][j]);        memset(d,0x3f,sizeof(d));    d[1][1][0]=0;    q.push(node{
     1,1,0,0});    while(!q.empty())    {        node t=q.top();q.pop();        if(d[t.x][t.y][t.d]
         
          n||fy>n) continue;            ll cost=t.w+T+(cur==0?dat[fx][fy]:0);            if(d[fx][fy][cur]>cost)                d[fx][fy][cur]=cost,q.push(node{fx,fy,cur,cost});        }    }        printf("%lld",min(d[n][n][0],min(d[n][n][1],d[n][n][2])));    return 0;}
         
        
       
      

 

B:

本来很基础的$dp$还纠结了一会状态的选择……

其实就是最长公共子序列：$dp[i][j]=dp[i-1][j-1]+1/max(dp[i-1][j],dp[i][j-1])$

#include 
      
       using namespace std;#define X first#define Y secondtypedef double db;typedef long long ll;typedef pair
       
         P;const int MAXN=1e3+10;int n,a[MAXN],b[MAXN],dp[MAXN][MAXN];int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",&a[i]);    for(int i=1;i<=n;i++) scanf("%d",&b[i]);        for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)        {            if(abs(a[i]-b[j])<=4)                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);            dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1]));        }    printf("%d",dp[n][n]);    return 0;}
       
      

如果从$dp[i][j]$向后转移答案依然是对的，但可能理解起来有些奇怪……

虽然$dp[i][j]$直接向$dp[i+1][j]/dp[i][j+1]$转移可能不是最优解，但一定能保证最优解存在

其实就是将上述直接取$max$的过程拆成两次更新

 

C:

此类偏序问题基本上都涉及到排序

可以发现将$l_i$排序后对于第$i$区间产生的关系数就是在该区间内$r_j$

#include 
      
       using namespace std;#define X first#define Y second#define pb push_backtypedef double db;typedef long long ll;typedef pair
       
         P;const int MAXN=2e5+10;int n,x,bit[MAXN];ll res=0;P dat[MAXN];void Update(int x){
     while(x<=2*n) bit[x]++,x+=x&(-x);}ll Query(int x){ll ret=0;while(x) ret+=bit[x],x-=x&(-x);return ret;}int main(){    scanf("%d",&n);    for(int i=1;i<=2*n;i++)    {        scanf("%d",&x);        if(!dat[x].X) dat[x].X=i;        else dat[x].Y=i;    }    sort(dat+1,dat+n+1);        for(int i=1;i<=n;i++)        res+=Query(dat[i].Y)-Query(dat[i].X-1),Update(dat[i].Y);    printf("%lld",res);    return 0;}