daily 3

CF 543A

类似完全背包

$dp[i][j]$ 表示 写了i行代码，还有j个可以当bug的空间，剩下的转移就很简单了

void solve(){
  int n,m,b;
  cin>>n>>m>>b>>MOD;
  vector<int>a(n+1);
  for(int i=1;i<=n;++i)cin>>a[i];
  vector dp(m+1,vector<ll>(b+1));//dp[i][j], have written i lines of code and the remaining free bugs is j ways
  dp[0][0]=1;
  for(int id=1;id<=n;++id){
    for(int i=1;i<=m;++i){
        for(int v=a[id];v<=b;++v){
            dp[i][v]+=dp[i-1][v-a[id]];
            dp[i][v]%=MOD;
        }
    }
  }
  ll ans=0;
  for(int i=0;i<=b;++i){
    ans=(ans+dp[m][i])%MOD;
  }
  cout<<ans<<'\n';
  return;
}

CF 557C

思维题，我们直接枚举那个最大的值，然后用一个$a[i]$数组来记录倒序的柱子高度，每次都计算一哈就可以了,复杂度O(n^2)

void solve(){
  int n;
  cin>>n;
  vector<ll>l(n+2),d(n+2);
  for(int i=1;i<=n;++i)cin>>l[i];
  for(int i=1;i<=n;++i)cin>>d[i];
  vector<pair<ll,ll>>a(n+2),b(n+2);
  for(int i=1;i<=n;++i){
    a[i]=make_pair(d[i],l[i]);
    b[i]=make_pair(l[i],d[i]);
  }
  a[0]=b[0]=make_pair(0,0);
  a[n+1]=b[n+1]=make_pair(INT_MAX,INT_MAX);
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  int len=0;
  ll p=0,rem=0;
  for(int i=1;i<=n;++i){
    ++len;
    p+=b[i].second;//p represent the total remaining of the same height
    if(b[i].first!=b[i+1].first){
        int sub=n;
        while(sub&&len>1){//keep no more than len's other shit
            if(a[sub].second<b[i].first){
                p+=a[sub].first;
                --len;
            }
            --sub;
        }
        rem=max(rem,p);
        p=len=0;
    }
  }
  ll sum=accumulate(d.begin(),d.end(),0ll);
  cout<<sum-rem<<'\n';
  return;
}

CF 571B

傻子都知道(我不知道)要分成n/k长度的和n/k +1长度的两种数组，分别转移即可

nt n,k;
int pos(int i,int j){
    return i*(n/k)+j;
}
void solve(){
  cin>>n>>k;
  int r=n%k;
  vector<int>a(n+1);
  for(int i=1;i<=n;++i)cin>>a[i];
  sort(a.begin()+1,a.end());
  vector dp(k+1,vector<ll>(k+1,INF));
  dp[0][0]=0;
  for(int i=1;i<=k;++i){
    for(int j=0;j<=min(r,i);++j){
       if(j){
            dp[i][j]=min(dp[i-1][j]+a[pos(i,j)]-a[pos(i-1,j)+1],dp[i-1][j-1]+a[pos(i,j)]-a[pos(i-1,j-1)+1]);
       }else{
            dp[i][j]=dp[i-1][j]+a[pos(i,j)]-a[pos(i-1,j)+1];
       }
    }
  }
  cout<<dp[k][r]<<'\n';
  return;
}