dp practice_day 6

今天总感觉写的有点想吐，就只写2题然后去写LSM了(明天补上剩下的)

CF 1067A

首先还是确定状态状态，先看数据的范围1-200那么我们可以包含当前的值的所有情况来做我们的状态，然后考虑当前值和前面的值的关系，有= > <三种

那么我们令dp[i][j][0/1/2]为当前遍历到第i个元素，当前元素的取值为j，当前元素比前一个元素 相等/小于/大于的解

那么转移也很好实现

$dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2]$

$dp[i][j][2]=\sum_{k=1}^{j-1}{dp[i-1][k][0]+dp[i-1][k][1]+dp[i-1][k][2]}$

$dp[i][j][1]=\sum_{k=j+1}^{200}{dp[i-1][k][0]+dp[i-1][k][1]}$

需要注意的是计算小于的时候需要去掉前一个元素比前前个元素大的情况
另外对于第一个元素来说

ll dp[N][201][3];////0 eq, 1 less 2 greater
void solve(){
  int n;cin>>n;
  vector<int>a(n+1);
  for(int i=1;i<=n;++i)cin>>a[i];
  if(a[1]==-1){
    for(int i=1;i<=200;++i){
        dp[1][i][2]=1;
    }
  }else{
    dp[1][a[1]][2]=1;
  }

  for(int i=2;i<=n;++i){ 
    int sum=0;
    for(int j=1;j<=200;++j){
        if(a[i]==-1||a[i]==j){
            dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2])%MOD;
            dp[i][j][2]=sum%MOD;
        }
        sum=(sum+dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2])%MOD;
    }
    sum=0;
    //calculate less than previous
    for(int j=200;j>=1;--j){
        if(a[i]==-1||a[i]==j){
            dp[i][j][1]=sum%MOD;
        }
        sum=(sum+(dp[i-1][j][0]+dp[i-1][j][1]))%MOD;
    }
  }
  ll ans=0;
  for(int i=1;i<=200;++i){
    ans=(ans+(dp[n][i][0]+dp[n][i][1]))%MOD;
  }
  cout<<ans<<'\n';
  return;
}

CF 8C

首先看到数据范围，直接想到状压
那么转移也很好写了
需要注意的是每次只处理一次转移，然后break，不然会重复枚举，导致TLE

void solve(){
  int x,y;
  cin>>x>>y;
  int n;cin>>n;
  vector<int>a(n+1),b(a);
  a[n]=x,b[n]=y;
  for(int i=0;i<n;++i){
    cin>>a[i]>>b[i];
  }
  auto calc=[&](int i,int j){
    return abs(a[i]-a[j])*abs(a[i]-a[j])+abs(b[i]-b[j])*abs(b[i]-b[j]);
  };
  vector dis(n+1,vector<int>(n+1));
  for(int i=0;i<=n;++i){
    for(int j=0;j<=n;++j){
        dis[i][j]=calc(i,j);
    }
  }
  vector<int>pre(1<<(n+1));
  vector<int>dp(1<<(n+1),INF);
  dp[0]=0;
  for(int i=0;i<(1<<n);++i){
    if(dp[i]==INF)continue;
    for(int j=0;j<n;++j){
        if(((1<<j)&i)==0){
            for(int k=j;k<n;++k){
                if(((1<<k)&i)==0){
                    int d=dis[j][k]+dis[j][n]+dis[k][n];
                    int nxt=i|(1<<j)|(1<<k);
                    if(dp[nxt]>dp[i]+d){
                        dp[nxt]=dp[i]+d;
                        pre[nxt]=i;
                    }
                }
            }
        break;//just transfer first time
        }
    }
  }
  cout<<dp[(1<<n)-1]<<'\n';
  vector<int>ans;
  for(int i=(1<<n)-1;i!=0;i=pre[i]){
    ans.push_back(0);
    int tmp=pre[i]^i;
    int cnt=0;
    for(int j=0;j<n;++j){
        if((1<<j)&tmp){
            ans.push_back(j+1);
        }
    }
  }
  ans.push_back(0);
  for(int i=ans.size()-1;i>=0;--i){
    cout<<ans[i]<<" \n"[i==0];
  }
  return;
}

晚上看看SQL的代码吧，明天总结一下OS，哎，今天又摆了