问题标题: 洛谷2780题超时85分，请各位dalao看看啊！（dp蜜汁TLE）

#include<bits/stdc++.h>
using namespace std;
int a[1000];
int f[75100][260];
int b[100000];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    register int n,m,x,y,mmax=0,n1=0,ans=0;
    scanf("%d %d %d %d",&n,&m,&x,&y);
    for(register int i=1; i<=n; i++)
    scanf("%d",&a[i]);
    sort(a+1,a+n+1,cmp);
    for(register int i=1; i<=m; i++)
    {
        mmax+=a[i];
    }
    for(register int i=0; i<=mmax; i++)
    for(register int j=0; j<=m; j++)
    f[i][j]=-10000;
    f[0][0]=0;
    for(register int i=1; i<=n; i++)
    {
        for(register int k=mmax; k>=a[i]; k--)
        {
            for(register int j=1; j<=m; j++)
            f[k][j]=max(f[k][j],f[k-a[i]][j-1]+a[i]);
        }
    }
    for(register int i=1; i<=mmax; i++)
    if(f[i]>0)
    {
        b[++n1]=f[i][m];
    }
    for(register int i=x; i<=y; i++)
    {
        int my_max=10000000;
        for(register int j=1; j<=n1; j++)
        {
            if(abs(b[j]-i)<my_max)
            {
                my_max=abs(b[j]-i);
            }
        }
        if(my_max>ans) ans=my_max;
    }
    printf("%d",ans);
    return 0;
}

https://www.luogu.org/problemnew/show/P2780

求大佬解答！！！

有没有什么更优化的算法啊？

@葛新 @酷町喵~o( =∩ω∩= )o~  @王星河 @樊澄宇 @贾文卓 @杨喆 

陆麟瑞在2018-01-24 18:04:44追加了内容

题目是 [AHOI2016初中组]游戏

陆麟瑞在2018-01-24 20:46:58追加了内容

小雪与小可可正在玩一种数字游戏。他们准备了 n 张卡片，每一张卡片上都有一个整数。游戏开始后，小雪会先选择一个不小于 a 且不大于 b 的整数 t，并告诉小可可这个数字t 是多少。之后小可可会挑出恰好 k 张卡片，并将这 k 张卡片上的数字相加，得到的和数记为 m。

小雪希望 t 和 m 差的绝对值尽可能大，而小可可却希望 t 和 m 差的绝对值尽可能小。在游戏开始前，他们二人都知道 n， a， b 和 k 是多少，也知道每一张卡片上的数字是多少。在小雪决定了 t 的大小后，不能再修改，之后才由小可可挑选纸牌。

小雪希望知道，在二人都尝试最优策略的情况下， t 和 m 差的绝对值最大可以有多大？

输入输出格式

输入格式：

输入有两行。

第一行有 4 个整数 n， k， a 和 b，分别满足 1<=k<=n<=250 且0<=a<=b<=75000。

第二行有 n 个整数，依次为 x[1]到 x[n]，给出了每一张卡片上的数字。

每一张卡片上的数字 x[i]都满足 0<=x[i]<=300。

输出格式：

输出一行，只有一个整数，表示 t 和 m 差的绝对值最大可以有多大。

输入输出样例

输入样例#1： 复制

4 2 58 100
10 10 50 80

输出样例#1： 复制

15

输入样例#2： 复制

8 3 1300 1800
2 0 1 9 1 4 0 5

输出样例#2： 复制

1782

说明

对于 30%的数据， 1<=k<=n<=20 且 0<=a<=b<=6000。

对于 80%的数据， 1<=k<=n<=65 且 0<=a<=b<=19500。

对于 100%的数据， 1<=k<=n<=250 且 0<=a<=b<=75000。

陆麟瑞在2018-01-25 09:35:19追加了内容

@葛新 @酷町喵~o( =∩ω∩= )o~  @王星河 @樊澄宇 @贾文卓 @杨喆 @贾敬波 @许正全 @吴天意