Minimal Coverage

Minimal Coverage
题意：n根棒，按次序放置，后一根棒的起点为前一根棒的终点，可左右放置，求最后最小覆盖面积
思路：dp[i][j]为前 i 根棒放完后以终点位子 j 结束的最小覆盖面积。（最坏情况为最大长度*2）
状态转移方程：

if(j<=a[i])  dp[i][0]=min(dp[i][0],dp[i-1][j]+a[i]-j);//向左放（ai的长度向左放之后终点为负数了，则可以右端点向右移，使得左端点为0）
else  dp[i][j-a[i]]=min(dp[i][j-a[i]],dp[i-1][j]);//向左放
dp[i][j+a[i]]=min(dp[i][j+a[i]],max(dp[i-1][j],a[i]+j));//向右放

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=2e18+100;
const int maxn=1e4+100;
int a[maxn];
int dp[maxn][2100];
signed main()
{
	IOS
	int tt;
	cin>>tt;
	while(tt--)
	{
		int n;
		cin>>n;
		for(int i=1; i<=n; i++)
		{
			cin>>a[i];
		}
		for(int i=0; i<=n; i++)
		{
			for(int j=0; j<=2010; j++)
			{
				dp[i][j]=inf;
			}
		}
		dp[0][0]=0;
		for(int i=1; i<=n; i++)
		{
			for(int j=0; j<=2010; j++)
			{
				if(j<=a[i])
				{
					dp[i][0]=min(dp[i][0],dp[i-1][j]+a[i]-j);//向左放
				}
				else
				{
					dp[i][j-a[i]]=min(dp[i][j-a[i]],dp[i-1][j]);//向左放
				}
				dp[i][j+a[i]]=min(dp[i][j+a[i]],max(dp[i-1][j],a[i]+j));//向右放
			}
		}
		int ans=inf;
		for(int i=0; i<=2010; i++)
		{
			ans=min(ans,dp[n][i]);
		}
		cout<