2433.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<iostream>
using namespace std;

int a[50005];

int main()
{
   int t,n,x,y,min,l;
   scanf("%d",&t);
   for(int k=0;k<t;++k)
   {
      scanf("%d",&n);
      for(int i=0;i<n-1;++i) scanf("%d",&a[i]);
      l=a[n-2];
      for(int i=n-2;i>0;--i) a[i]-=a[i-1];        
      if(n<=3) printf("0\n");
      else
      {
         min=l+10;
         for(int i=1;i<n-2;++i)
            if(a[i]<min)
            {
               min=a[i];
               x=i+1;
               y=i+2;            
            }
         printf("%d\n",l+min);
         printf("%d 1 %d %d\n",y,n,x);
      }
      if(k!=t-1) printf("\n");
   }
}