web analytics

分糖果 动态规划

描述

whitecloth 有 N 个糖果,小猫 rainbow 和 freda 来找 whitecloth 要糖
吃……

对于每个糖果,rainbow 和 freda 各有一个喜欢度 ri 和 fi,whitecloth 不能不给他们糖果(他们会闹的),但又不想全给,于是 whitecloth 决定给他们恰好M 块糖果。

为了让两只小猫不要闹矛盾,whitecloth 希望所给糖果的ri 的和与 fi 的和的差值的绝对值尽量小,在此基础上,whitecloth 还希望所有 ri 和 fi 的总和最大,于是他请你来帮他出主意。

输入第一行两个数N,M
接下来 N 行,每行两个数ri,fi输出第一行一个数,表示最小的差值的绝对值
第二行一个数,表示最大的ri 和 fi 的总和。样例输入

样例输出

提示对于 30%的数据,N<=20,M<=10
对于 100%的数据,N<=200,M<=20,1<=ri,fi<=20,M<=N

 

分析:

这是道裸的DP

 

 

Post a Comment

You must be logged in to post a comment.