专栏首页随笔记录Berries DP CodeForces_1Berries348E Phoenix and

Berries DP CodeForces_1Berries348E Phoenix and

显然,同颜色的框会很多,而同树的框最多n个。即每棵树最多1个。

因为一旦一棵树的框多于1,其可以转化为多个同颜色框+1个同树框。

所以问题就变成了n个树,每棵树可以选择用不用同树框。这其实就是一个01背包的变形。

dp[i][j][k]表示执行到前i颗树,红色剩j个,蓝色剩k个,的状态,最大满筐数是多少。

这样是个n^4的dp,根据经验,可以省去蓝色的那一维,转而用总量减去红色剩余量来表示剩余的蓝色浆果。

所以:dp[i][j]表示执行到前i颗树,红色剩j个.的状态,最大满筐数是多少。

遍历i时,枚举s,表示这一同树框中放红色浆果s个,蓝色k-s个。枚举时保证合法性。

再枚举j,用dp[i-1][j]来更新当前状态。

设nm1表示当前装s个红色浆果到同树框后,红色浆果剩余量,显然:nm1=j+a[i]-s,

sm表示1-i树上总浆果数

同理nm2表蓝色剩余,nm2=sm-dp[i-1][j]*k-k-nm1.

然后考虑转移:dp[i][nm1%k]=max(dp[i][nm1%k],dp[i-1][j]+nm1/k+nm2/k+1); 即装完同树框后,看蓝色与红色能否再装同色框。

枚举完s时加上一个当前数不装同树框的转移即可。

结果为dp[n][j]最大值。

这里注意一个细节。。int取模比long long 快个常数,这题刚好卡这个。。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int M = 500+7;

ll dp[M][M];//前i棵树,剩j个红浆果的状态,最大装筐数

int a[M],b[M];

int main()

{

int n,k;

cin>>n>>k;

for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);

memset(dp,-1,sizeof(dp));

ll sm=0;

dp[0][0]=0;

for(int i=1;i<=n;i++)

{

sm+=a[i]+b[i];

for(int j=0;j<k;j++)

{

if(dp[i-1][j]<0)continue;//不合法状态不能往后转移

for(int s=1;s<k&&s<=a[i];s++)//这一筐装红浆果多少个

{

if(k-s>b[i])continue;//必须合法

int nm1=j+a[i]-s;//红浆果剩余量

int nm2=sm-dp[i-1][j]*k-nm1-k;

dp[i][nm1%k]=max(dp[i][nm1%k],dp[i-1][j]+nm1/k+nm2/k+1);

// cout<<i<<" “<<j<<” “<<s<<” nm1 = “<<nm1<<” nm2 = “<<nm2<<” “<<sm<<” “<<k-s<<” “<<dp[i][nm1%k]<<endl;

}

int nm1=j+a[i],nm2=sm-dp[i-1][j]*k-nm1;//用int更快

// cout<<i <<” “<<j<<” = “<<nm1<<” – “<<nm2<<” "<<sm<<endl;

dp[i][nm1%k]=max(dp[i][nm1%k],dp[i-1][j]+nm1/k+nm2/k);//当前树不装 同一树类型的筐

}

}

ll ans=0;

for(int j=0;j<k;j++)ans=max(ans,dp[n][j]);

cout<<ans<<endl;

return 0;

题意:

把字符串 sss 中的字符分给 kkk 个空字符串,要求每个空字符串都有字符,同时最小化 kkk 个字符串中字典序的最大值,输出分配后字典序最大的字符。

分类讨论,如果 sss 排序后,s0=sk−1s_0=s_{k-1}s

0

=s

k−1

答案就是 sk−1s_{k-1}s

k−1

, 如果相等且 [k,n−1][k,n - 1][k,n−1] 只有一种字符,就要把这种字符依此分给每个字符串,输出最大的. 如果相等但是 [k,n−1][k,n - 1][k,n−1] 多种字符,就把 k−1k-1k−1 后面的所有字符加在 s0s_0s

0

————————————————

版权声明:本文为CSDN博主「w4979」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。

原文链接:https://blog.csdn.net/w4979/java/article/details/105900607

原文链接:https://blog.csdn.net/w4979/article/details/105900607

我来说两句

0 条评论
登录 后参与评论

相关文章

  • public static Object service(String url, World至浏览

    生产环境,已经运行了好几年,一直没有问题。最近频繁奔溃(一般是连续运行好几天才奔溃一次)。boost 返回的 奔溃显示是 invaild_charset gbk...

    w4979的博客
  • Berries DP CodeForces_1Berries348E Phoenix and

    所以问题就变成了n个树,每棵树可以选择用不用同树框。这其实就是一个01背包的变形。

    w4979的博客
  • of baskets he can fill completely!Help Phoenix determine the maximum number

    Problem Description Phoenix is picking berries in his backyard. There are n shr...

    w4979的博客
  • public static Object service(String url, World至浏览

    生产环境,已经运行了好几年,一直没有问题。最近频繁奔溃(一般是连续运行好几天才奔溃一次)。boost 返回的 奔溃显示是 invaild_charset gbk...

    w4979的博客
  • Berries DP CodeForces_1Berries348E Phoenix and

    所以问题就变成了n个树,每棵树可以选择用不用同树框。这其实就是一个01背包的变形。

    w4979的博客
  • LWC 51:684. Redundant Connection

    LWC 51:684. Redundant Connection 传送门:684. Redundant Connection Problem: We are ...

    用户1147447
  • BZOJ4241: 历史研究(回滚莫队)

    如果询问的两个端点在同一个块中,直接暴力计算,时间复杂度$O(\sqrt{n})$

    attack
  • ZOJ 3331 Process the Tasks(双塔DP)

    Process the Tasks ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- The...

    ShenduCC
  • OpenCV中直方图反向投影算法详解与实现

    OpenCV中直方图反向投影算法详解与实现 一:直方图交叉 OpenCV中直方图反向投影算法实现来自一篇论文《Indexing Via Color Histog...

    OpenCV学堂
  • LintCode-463.整数排序

    给一组整数,按照升序排序,使用选择排序,冒泡排序,插入排序或者任何 O(n2) 的排序算法。

    悠扬前奏

扫码关注云+社区

领取腾讯云代金券