#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,t,k,p=5000,x,y,z,v[3004],w[3004],b[3004],dp[3004],g[3004],q[3004];
int main()
{
    scanf("%d%d%d%d",&n,&m,&t,&k);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        v[i]=y;
        w[i]=z-x;
    }
    for(int i=1;i<=k;i++){
        scanf("%d",&x);
        b[x]=1;
        p=min(p,x);
    }
    g[p]=1;
    q[p]=p;
    for(int i=p+1;i<=t;i++){
        dp[i]=dp[i-1];
        g[i]=g[i-1]+1;
        q[i]=q[i-1];
        if(b[i]==1){
            for(int j=1;j<=m;j++){
                if(i>=v[j] && dp[i-v[j]]+w[j]>=dp[i] && g[i-v[j]]+v[j]>i-q[i-v[j]]){
                    dp[i]=dp[i-v[j]]+w[j];
                    g[i]=v[j];
                    q[i]=q[i-v[j]];
                }
            }
            q[i]=i;
        }
    }
    printf("%d",dp[t]*n);
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<string>
#define ll long long
#define inf 214748364
#define DB double
using namespace std;
ll n,m,t,k,f[20002],onl[20002];
struct P{
ll T,v;
}a[2003];
bool cmp(P x,P y)
{
if(x.T!=y.T) return x.T<y.T;
else return x.v>y.v;
}
int main()
{
//首先是个贪心，对于n块地,如果我知道种那一种菜
//是最优的，那么我就可以把这n块地都种上最优的那
//种菜
scanf("%lld%lld%lld%lld",&n,&m,&t,&k);
for(ll i=1;i<=m;i++)
{
ll x,y;
scanf("%lld%lld%lld",&x,&a[i].T,&y);
a[i].v=y-x;//把每一种菜的价格和收获放一起
//排序找最优的

//cout<<a[i].v<<"T "<<endl;
}
//一定要注意变量类型
sort(a+1,a+m+1,cmp);
for(ll i=1;i<=k;i++)
{
scanf("%lld",&onl[i]);
if(onl[i]==t) onl[i]=0;
//以题目要求，归到下一天里
}
sort(onl+1,onl+k+1);
//谁上线不是按时间来呢
for(ll i=2;i<=k;i++)
{
ll id=1;//从第一种菜开始找起
for(ll j=i-1;j>=1 && id<=m;j--)//用之前的时间更新现在的
{
while(onl[i]-onl[j]>=a[id].T)
{
f[i]=max(f[i],f[j]+a[id].v*n);
id++;
}//如果放的菜可以的话，那我就枚举一下放哪种菜
//直到不可以放为止
}

}
printf("%lld",f[k]);
return 0;
}

为什么8,9，10个点运行超时

为什么要排序？

if f[j]=k) then

begin

if f[j]

我水死，不懂O(K^2)的算法，

只能暴力预处理，然后来个o(mk)的算法....

加上减枝，额，写了120行...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

动归太弱了 感觉挺好的一个题目

外挂！！！

#include

#include

using namespace std;

int f[3010],v[3010],u[3010];

void qsort(int l,int r)

{

int i=l,j=r,mid=v[(i+j)/2];

do

{

while(v[i]mid) j--;

if(i

Accepted 有效得分：100 有效耗时：41ms

最后一次收获要上线......

在这里WA了一次

for (int i = 0; i

ls果然好思想

var

f,u,v:array[0..3000]of longint;

i,j,a,b,c,d,o,p,q:longint;

procedure swap(x,y:longint);

var r:longint;

begin

r:=v[x];

v[x]:=v[y];

v[y]:=r;

end;

procedure qsort(left,right:longint);

var ti,tj,mid:longint;

begin

if left>=right then exit;

ti:=left; tj:=right;

mid:=v[(ti+tj)div 2];

repeat

while v[ti]mid do dec(tj);

if titj;

qsort(left,tj);

qsort(ti,right);

end;

begin

assign(input,'1.txt');

reset(input);

assign(output,'2.txt');

rewrite(output);

readln(a,b,c,d);

fillchar(u,sizeof(u),0);

v:=u;

f:=u;

for i:=1 to b do

begin

readln(o,p,q);

if q-o>u[p] then u[p]:=q-o;

end;

for i:=1 to c-1 do if u[i]q then q:=f[j]+u[v[i]-v[j]];

f[i]:=q;

end;

writeln(f[d]*a);

close(input);

close(output);

end.

同志们 都是这个循环变量 太讨厌了! 我的正确率啊.

还好在我不断努力之下,还是A了.

晒晒

var v,i,j,n,m,k,r,l,o,p:longint;

a,b,c,t,g:array[0..3000] of longint;

procedure kp(q,w:longint);

var i,j,k,p:longint;

begin

i:=q;

j:=w;

k:=t[(q+w) div 2];

repeat

while t[i]k do dec(j);

if ij;

if j>q then kp(q,j);

if ib[j] then begin v:=b[i];b[i]:=b[j];b[j]:=v;end;

kp(1,m);

for i:=2 to k do

begin

g[i]:=0;o:=i-1;

for j:=1 to m do

begin

while (b[i]-b[o]0) do dec(o);

if o=0 then break;

if g[i]

好灵异啊！我小号AC的程序在我大号里居然有7个错误答案！怀疑我的RP

第100道啦，庆祝下！

第一行有三个正整数n,m,t,k

牛

第一次搞了一个没+任何优化的朴素DP...3个点TLE....+了个break..时间挺快的...

注意啊，给出的上线时间要排序

在此立碑，纪念千年一次的打错快排

囧题~

看不懂~

欺负我不玩网页游戏~！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

千错万错 ，都是‘0’惹的祸!!!!!!!!!!!!