6 3 5 9 12 15 17 6 3 5 9 12 30 40
3 -1
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const INF = 0x3fffffff;
int const MAX = 100005;
int dp[MAX][2], x[MAX];
bool has[MAX * 10];
int main()
{
int n;
while(scanf("%d", &n) != EOF && n)
{
int ans = -1;
bool flag = false;
memset(has, false, sizeof(has));
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; i++)
{
scanf("%d", &x[i]);
has[x[i]] = true;
}
if(n == 2)
{
printf("0\n");
continue;
}
dp[0][0] = x[0];
dp[0][1] = x[1];
for(int i = 1; i < n; i++)
{
for(int j = 2; j <= 10; j++)
{
int d0 = dp[i - 1][0] + j;
if((has[d0] || d0 >= x[n - 1]) && d0 > dp[i - 1][1])
{
for(int k = 2; k <= 10; k++)
{
if(dp[i - 1][1] + k > d0 && (has[dp[i - 1][1] + k] || dp[i - 1][1] + k >= x[n - 1]))
{
dp[i][0] = max(dp[i][0], d0);
break;
}
}
}
}
for(int j = 2; j <= 10; j++)
{
int d1 = dp[i - 1][1] + j;
if((has[d1] || d1 >= x[n - 1]) && d1 > dp[i][0])
{
for(int k = 2; k <= 10; k++)
{
if(dp[i][0] + k > d1 && (has[dp[i][0] + k] || dp[i][0] + k >= x[n - 1]))
{
dp[i][1] = max(dp[i][1], d1);
break;
}
}
}
}
}
for(int i = 1; i < n; i++)
{
if(dp[i][0] >= x[n - 1])
{
flag = true;
printf("%d\n", 2 * i - 1);
break;
}
if(dp[i][1] >= x[n - 1])
{
flag = true;
printf("%d\n", 2 * i);
break;
}
}
if(!flag)
printf("-1\n");
}
}版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/tc_to_top/article/details/46872773