本人用的区间DP，TLE90分，不知道是不是思路错了，求助

本人的屎山代码：

#include <bits/stdc++.h>
using namespace std;
const int N=3000+10;

int n,k;
int a[N];
int dp_min[N][N];
int dp_max[N][N];

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++) dp_max[i][i]=a[i]/k;
	for(int i=1;i<=n;i++) dp_min[i][i]=a[i]/k;
	for(int len=2;len<=n;len++)
	{
		for(int l=1;l<=n-len+1;l++)
		{
			int r=l+len-1;
			
			dp_max[l][r]=0x3f3f3f3f;

			for(int i=1;i<=k;i++)
			{
				int res,c,mx,mn;

				res=a[l]/i;
				mx=max(res,dp_max[l+1][r]);
				mn=min(res,dp_min[l+1][r]);
				if(mx-mn<=dp_max[l][r]-dp_min[l][r])
				{
					dp_max[l][r]=mx;
					dp_min[l][r]=mn;
				}

				res=a[r]/i;
				mx=max(res,dp_max[l][r-1]);
				mn=min(res,dp_min[l][r-1]);
				if(mx-mn<=dp_max[l][r]-dp_min[l][r])
				{
					dp_max[l][r]=mx;
					dp_min[l][r]=mn;
				}

			}
			//printf("dp_max[%d][%d]=%d;dp_min[%d][%d]=%d\n",l,r,dp_max[l][r],l,r,dp_min[l][r]);
		}
	}
	cout<<dp_max[1][n]-dp_min[1][n]<<endl;
	return 0;
}