10337

It’s a bottom up dp approach.

#include <iostream>
#include <cstdio>
#include <queue>
#include <sstream>
#include <string>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>

#define INF 100000000

using namespace std;
vector<int> vb[11];
vector<int> v;
int dp[11][1010];

void init()
{
	for(int i=0;i<11;i++)
	{
		vb[i].clear();
		for(int j=0;j<1010;j++)
		{
			dp[i][j]=-1;
		}
	}
}

int _min(int a,int b,int c,int d)
{
	v.clear();
	v.push_back(a);
	v.push_back(b);
	v.push_back(c);
	v.push_back(d);
	sort(v.begin(),v.end());
	return v[0];
}

int mn(int a,int b,int c)
{
	v.clear();
	v.push_back(a);
	v.push_back(b);
	v.push_back(c);
	sort(v.begin(),v.end());
	return v[0];
}
int main()
{
	int t,X,slot,a,b,c,d;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&X);
		init();
		slot = X/100;
		for(int i=9;i>=0;i--)
		{
			for(int j=0;j<slot;j++)
			{
				scanf("%d",&a);
				vb[i].push_back(a);
			}
		}
		dp[0][1]=30-vb[0][0];
		dp[1][1]=60-vb[0][0];
		for(int i=2;i<=slot;i++)
		{
			for(int j=0;j<=9;j++)
			{
				if(j>0 && j<9)
				{
					if(dp[j-1][i-1]==-1)a = INF;
					else a = dp[j-1][i-1]+60-vb[j-1][i-1];

					if(dp[j][i-1]==-1)b = INF;
					else b = dp[j][i-1]+30-vb[j][i-1];

					if(dp[j+1][i-1]==-1)c = INF;
					else c = dp[j+1][i-1]+20-vb[j+1][i-1];

					if(dp[j][i]==-1)d = INF;
					else d = dp[j][i];
					dp[j][i]=_min(a,b,c,d);//_min( dp[j-1][i-1]+60-vb[j-1][i-1], dp[j][i-1]+30-vb[j][i-1], dp[j+1][i-1]+20-vb[j+1][i-1] );
				}
				else if(j==9)
				{
					if(dp[j-1][i-1]==-1)a = INF;
					else a = dp[j-1][i-1]+60-vb[j-1][i-1];

					if(dp[j][i-1]==-1)b = INF;
					else b = dp[j][i-1]+30-vb[j][i-1];

					if(dp[j][i]==-1)c = INF;
					else c = dp[j][i];
					dp[j][i]=mn(a,b,c);//_min( dp[j-1][i-1]+60-vb[j-1][i-1], dp[j][i-1]+30-vb[j][i-1] );
				}
				else if(j==0)
				{
					if(dp[j][i-1]==-1)a = INF;
					else a = dp[j][i-1]+30-vb[j][i-1];

					if(dp[j+1][i-1]==-1)b = INF;
					else b = dp[j+1][i-1]+20-vb[j+1][i-1];

					if(dp[j][i]==-1)c = INF;
					else c = dp[j][i];

					dp[j][i]=mn(a,b,c);//_min( dp[j][i-1]+30-vb[j][i-1], dp[j+1][i-1]+20-vb[j+1][i-1] );
				}
			}
		}
		cout<<dp[0][slot]<<"\n\n";
	}
	return 0;
}