[2017纪中10-30]Group DP+差分优化_DOFYPXY的博客-程序员秘密

题面
考虑先将数组排序，从左往右一个个分组，每一组的极差拆成：-第一个加进该组的数（-a[l]）+最后一个加进该组的数（+a[r]）。于是设计状态f[i][j][k]表示分到第i个，有j个只填了开始没填结束，当前极差和为k。但这样k的范围会很大。
考虑差分优化，把-a[l]+a[r]写成（-a[l]+a[l+1]）+(-a[l+1]+a[l+2])+…+(-a[r-1]+a[r])。于是在转移时，每一个未分完的组都要加a[i]-a[i-1]。
具体的：设v=j*(a[i]-a[i-1])+k。f[i-1][j][k]可以转移到四种情况：
a[i]新建一组不作为结束：f[i][j+1][v]+=f。
a[i]新建一组作为结束：f[i][j][v]+=f。
a[i]加入旧组不作为结束：f[i+1][j][v]+=f*j。
a[i]加入旧组作为结束：f[i+1][j-1][v]+=f*j。
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define up(a,b) a=((a)+(b))%mod
using namespace std;
int n,mxk,a[210];
ll f[2][210][1010];
const int mod=1000000007;
int main()
{
    scanf("%d%d",&n,&mxk);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);    
    f[0][0][0]=1;   
    for(int i=0;i<n;i++)
    {
        int b=i&1,s=0;
        memset(f[b^1],0,sizeof(f[b^1]));
        for(int j=0;j<=i;j++,s+=a[i+1]-a[i])
            for(int k=0;k<=mxk-s;k++)
            {
                up(f[b^1][j+1][k+s],f[b][j][k]);
                up(f[b^1][j][k+s],f[b][j][k]);
                up(f[b^1][j][k+s],f[b][j][k]*j%mod);
                if(j>0)up(f[b^1][j-1][k+s],f[b][j][k]*j%mod);
            }
    }
    ll ans=0;
    for(int k=0;k<=mxk;k++)
        up(ans,f[n&1][0][k]);           
    printf("%lld",ans); 
    return 0;
}

本文链接：https://blog.csdn.net/DOFYPXY/article/details/78396490

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

entity、bo、vo、po、dto、pojo如何理解和区分？_weixin_34362991的博客-程序员秘密

Java开发过程中，基本实体类包都以entity或者model来称呼，可是不少项目中，却以Bo、Vo来命名，面试的时候，也有可能被问到这些问题。那么，这几者分别代表什么意思呢？Entity最常用实体类，基本和数据表一一对应，一个实体一张表。Bo(business object)代表业务对象的意思，Bo就是把业务逻辑封装为一个对象（注意是逻辑，业务逻辑），这个对象可以包括一个或多个其它的对象。通过调...

JavaScript的type属性等于text/html 例子_"js type\"text/html"_catoop的博客-程序员秘密

在使用javascript标签的时候，其中type最常用的就是

深入理解计算机系统之链接（三）_godspeedkaka的博客-程序员秘密

静态库的概念静态库就是由一组独立的可重定向目标文件封装而成的，在Unix系统中，静态库以一种称为归档(archive)的特殊文件存放在磁盘上。存档文件是一组连接起来的可重定位目标文件的集合，有一个头部用来描述每个目标文件的大小和位置，存档文件名有后缀.a表示链接器如何使用静态库来解析引用在符号解析的阶段，链接器从左到右按照他们在编译器驱动程序命令行上出现的相同顺序来扫描可重定位目标文件和存档文件。（

后台怎样获取前台input的值？_大爱李志的博客-程序员秘密

在前台input中加入 runat="server"在后台中String ss = Request.Form["start"];

redis-desktop-manager的使用_在京奋斗者的博客-程序员秘密

实际工作环境中，Redis会安装在服务器上，我们想使用Redis服务就要使用Redis终端。 redis-desktop-manager便是来连接Redis服务并可供我们学习使用的。首先，安装 redis-desktop-manager，大家可以到http://download.csdn.net/detail/u012453843/9820194这个地址下载安装包并进行安装。

code art_coekaa826620的博客-程序员秘密

PART ONE============= public void doGet(HttpServletRequest request, HttpServletResponse response) throws Servlet...