C++14(g++5.4) 解法, 执行用时: 320ms, 内存消耗: 160872K, 提交时间: 2020-05-23 14:10:49

#include <bits/stdc++.h>
#define MAXN 100005
#define MOD 1000000007
#define INF 1000000000000000
using namespace std;
int N,M,K;
struct node{
int ti=-1;
long long v=-1;
friend bool operator <(node a,node b)
{
    if(a.v!=b.v)return a.v>b.v;
    return a.ti>b.ti;
}
};
node bin[MAXN];
long long dp[MAXN][203];
int main()
{
   //freopen("testdata.in","r",stdin);
   cin>>N>>M>>K;
   long long sum=0;
   for(int i=1;i<=K;i++)
   {
       int f,t;long long w;
       cin>>f>>t>>w;
       node sub;sub.ti = t,sub.v = w;
       if(sub < bin[f])bin[f]=sub;
       sum += sub.v;
   }
   memset(dp,127,sizeof(dp));
   dp[1][0] = 0;
   for(int i=1;i<=N;i++)
      for(int j=0;j<=M;j++)
   {
       if(dp[i][j]>=INF)continue;
       if(bin[i].ti==-1)
       {
           dp[i+1][j]=min(dp[i][j],dp[i+1][j]);
       }
       else
       {
       if(j<200)dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);
       dp[bin[i].ti+1][j] = min(dp[bin[i].ti+1][j],dp[i][j]+bin[i].v);
       }
   }
   long long mint = INF;
   for(int i=0;i<=M;i++)
       mint=min(dp[N+1][i],mint);
   cout<<sum-mint<<endl;

   return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 191ms, 内存消耗: 165608K, 提交时间: 2020-05-23 14:53:21

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int read()
{
	int res = 0, f = 1; char c = getchar();
	while(!isdigit(c) && c != '-') c = getchar();
	if(c == '-') f = -1, c = getchar();
	while(isdigit(c)) res = (res<<3)+(res<<1)+(c^48), c = getchar();
	return res*f;
}

const int maxn = 1e5+10;
const LL inf = 4e18;
int n, m, k, nt[maxn], w[maxn];
LL sum, dp[maxn][210];

int main()
{
	n = read(); m = read(); k = read();
	for(int i = 1; i <= n; i++) nt[i] = i+1;
	for(int i = 1, u, v, d; i <= k; i++)
	{
		u = read(); v = read()+1; d = read();
		sum += d;
		if(w[u] < d || (w[u] == d && nt[u] < v))
		{
			nt[u] = v;
			w[u] = d;
		}
	}
	
	for(int i = 2; i <= n+1; i++)
	for(int j = 0; j <= m; j++) dp[i][j] = inf;
	
	for(int i = 1; i <= n; i++)
	for(int j = 0; j <= m; j++)
	{
		if(j > i-1) break;
		dp[nt[i]][j] = min(dp[nt[i]][j], dp[i][j]+w[i]);
		if(j < m) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]);
	}
	
	LL ans = inf;
	for(int i = 0; i <= m; i++) ans = min(ans, dp[n+1][i]);
	ans = sum-ans;
	printf("%lld\n", ans);
	return 0;
}