这道题好几天前就写出了记搜代码，但是理论上空间恰好够，实际上不论是用new-delete还是malloc-free，都有1~2个点MLE了（最抽象的是一开始MLE两个点，我把数组两个下标调换顺序后理应得到相同的分数，但实际上...竟然变成只MLE一个点了...离谱至极），看来动态内存不是那么好使，他们实际上干的活肯定和教科书上写的不一样，他们一定背着我偷偷多申请了空间才会导致MLE。
意识到记搜的缺点是不能利用滚动数组思想把空间消耗从n*n变成n，于是不得不改写成递推式动归，但是突然身体很难受，休息了几天，今早起来挺着写了一小会代码，把这道题AC了...毕竟不能把一道题拖太久...
90分记搜Code
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
using namespace std;
#define int long long
int ** DP;
int dfs(int ct,int m,const int * const a,const int * const b)//ct is counted_time,m is drug
{
if(ct==0)return 0;
if(m==0) return 0;
if(m==1) return DP[ct-1][m-1]=ct/a[m-1]*b[m-1];
if(DP[ct-1][m-1]!=-1)return DP[ct-1][m-1];
int DFS=0;
for(int i=0;i<=ct/a[m-1];i++)
DFS=max(DFS,dfs(ct-i*a[m-1],m-1,a,b)+i*b[m-1]);
return DP[ct-1][m-1]=DFS;
}
signed main()
{
//初始化
int t,m,*a,*b;
cin>>t>>m;
DP=(int**)malloc(sizeof(int*)*(t));
for(int i=0;i<t;i++)
DP[i]=(int*)malloc(sizeof(int)*(m));
for(int i=0;i<t;i++)
for(int j=0;j<m;j++)
DP[i][j]=-1;
a=(int*)malloc(sizeof(int)*(m));
b=(int*)malloc(sizeof(int)*(m));
for(int i=0;i<m;i++)
cin>>a[i]>>b[i];
//运算
cout<<dfs(t,m,a,b)<<endl;
//delete
for(int i=0;i<t;i++)
free(DP[i]);
free(DP);free(a);free(b);
return 0;
}
/*超128MBMLE点（理论上不该MLE，t*m<1e7）
10000000 1
1 10000
*/
AC-传统DP-Code
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
using namespace std;
#define int long long
int *DP;
signed main()
{
//初始化
int t,m,*a,*b;
cin>>t>>m;
DP=(int*)malloc(sizeof(int)*(t+1));
a=(int*)malloc(sizeof(int)*(m+1));
b=(int*)malloc(sizeof(int)*(m+1));
for(int i=1;i<=m;i++)
cin>>a[i]>>b[i];
DP[0]=0;
for(int i=1;i<=t;i++)DP[i]=i/a[1]*b[1];
for(int i=2;i<=m;i++)
{
for(int j=1;j<=t;j++)
{
int DFS=0;
for(int k=0;k<=j/a[i];k++)
DFS=max(DFS,DP[j-k*a[i]]+k*b[i]);
DP[j]=DFS;
}
}
cout<<DP[t]<<endl;
free(DP);free(a);free(b);
return 0;
}