dp practice_day 5

CF 347 C

一道记忆化搜索题，没太多好说的，注意记忆化搜索的方式以及vis数组的更改

void solve(){
  int n,m;cin>>n>>m;
  auto check=[&](int x,int y){
    return x>=1&&x<=n&&y>=1&y<=m;
  };
  vector<vector<char>>mp(n+1,vector<char>(m+1));
  vector<vector<bool>>vis(n+1,vector<bool>(m+1,false));
  vector<vector<int>>dis(n+1,vector<int>(m+1));
  auto check_char=[&](int x,int y,int tx,int ty){
    return mp[x][y]=='D'&&mp[tx][ty]=='I'||mp[x][y]=='I'&&mp[tx][ty]=='M'||mp[x][y]=='M'&&mp[tx][ty]=='A'||mp[x][y]=='A'&&mp[tx][ty]=='D';
  };
  for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
        cin>>mp[i][j];
    }
  }
  int ans=0;
  function<void(int,int)>dfs=[&](int x,int y){
    if(dis[x][y])return;
    vis[x][y]=1;
    dis[x][y]=1;
    for(int i=0;i<4;++i){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(!check(tx,ty)||!check_char(x,y,tx,ty))continue;
        if(vis[tx][ty]){
            cout<<"Poor Inna!\n";
            exit(0);
        }
        dfs(tx,ty);
        dis[x][y]=max(dis[x][y],dis[tx][ty]+1);
    }
    vis[x][y]=0;
  };
  for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
        if(mp[i][j]=='D'&&!vis[i][j]){//did not appear in other situation
            dfs(i,j);
            ans=max(dis[i][j],ans);
        }
    }
  }
  ans/=4;
  if(ans==0){
    cout<<"Poor Dima!\n";
  }else{
    cout<<ans<<'\n';
  }
  return;
}

CF 402D

刚开始看到的时候有点不好下手

首先我们判断，肯定是要从后往前进行操作，因为从前往后的话会导致你之后的操作无效(前面都变成gcd=1了)
题目中的f的值就是这个数含有的good prime数量 -bad prime数量
对应去求即可

int a[N],g[N];
int gcd(int a,int b){
  return b==0 ? a : gcd(b,a%b);
}
set<int>bad;
pii get_pair(int x){
    int posi=0,neg=0;
    for(int i=2,t=sqrt(x);i<=t;++i){
        int cnt=0;
        while(x%i==0){
            x/=i;
            ++cnt;
        }
        if(!cnt)continue;
        if(bad.count(i)){
            neg+=cnt;
        }else{
            posi+=cnt;
        }
    }
    if(x!=1){
        if(bad.count(x)){
            neg++;
        }else{
            posi++;
        }
    }
    return pii(posi,neg);
};
bool check(int x){
    pii pr=get_pair(x);
    return pr.first<pr.second;
}
void solve(){
  int n,m;cin>>n>>m;
  for(int i=1;i<=n;++i){
    cin>>a[i];
    if(i==1){
        g[i]=a[i];
    }else{
        g[i]=gcd(a[i],g[i-1]);
    }
  }
  for(int i=1;i<=m;++i){
    int x;cin>>x;
    bad.insert(x);
  }

  int ans=0,d=1;
  for(int i=n;i>=1;--i){
    if(check(g[i]/d)){
        d=g[i];
    }
    a[i]/=d;
  }
  for(int i=1;i<=n;++i){
    pii pr=get_pair(a[i]);
    ans+=pr.first-pr.second;
  }
  cout<<ans<<'\n';
  return;
}

CF 703J

一开始也是完全没头绪，ans1很好求，就是把杯子按照体积排序，然后选杯子就可以了

ans2的话，看题解发现是用01背包

令dp[i][j][k]为前i个杯子，选了j个，总体积为k的不移动的水的最大值，那么有以下转移
dp[j][k]=max(dp[j][k],dp[j-1][k-now_vol]+now_rem)
注意要逆序枚举,因为是01背包

struct bt{
    int rem,vol;
};
void solve(){
  int n;cin>>n;
  vector<bt>a(n+1);
  ll total=0;
  for(int i=1;i<=n;++i){
    cin>>a[i].rem;
    total+=a[i].rem;
  }
  for(int i=1;i<=n;++i){
    cin>>a[i].vol;
  }
  sort(a.begin()+1,a.end(),[&](bt a,bt b){
    return a.vol>b.vol;
  });
  int ans1=0;
  ll sum=0;
  while(total>sum)sum+=a[++ans1].vol;
  vector dp(n+1,vector<ll>(sum+1,-1000000));
  dp[0][0]=0;
  for(int i=1;i<=n;++i){
    for(int j=ans1;j>=1;--j){
        for(ll k=sum;k>=a[i].vol;--k){
            dp[j][k]=max(dp[j][k],dp[j-1][k-a[i].vol]+a[i].rem);
        }
    }
  }
  ll ans2=0;
  for(int i=total;i<=sum;++i){
    ans2=max(ans2,dp[ans1][i]);
  }
  cout<<ans1<<' '<<total-ans2<<'\n';
  return;
}

明天复习OS，写一下在NU上的CS的笔记吧，惹啊！