U2

#include <iostream>

#define MAXN 100
using namespace std;

int t[MAXN] = { 0, 5, 2, 7, 8, 3, 9, 4, 2 };
int s[MAXN] = { 0, 6, 3, 10, 12, 8, 8, 6 }, M[MAXN], N = 8;

int opt()
{   M[1]=t[1];
    M[2]=t[1]+t[2];
    if(M[2]>s[1]) M[2]=s[1];
    for(int i=3;i<=N;i++)
    {  M[i]=t[i]+M[i-1];
       if(M[i]>s[i-1]+M[i-2])
          M[i]=s[i-1]+M[i-2];
    }
    return M[N];
}

void restore(int i)
{ if(i==1) {printf("(1) ");return;}
  if(i==2)
  {  if(M[2]==t[1]+t[2])
     { printf("1 2 ");return;}
     else { printf("(1 2) " );return;};
  }
  if(M[i]==t[i]+M[i-1])
  { restore(i-1); printf("(%d) ",i);}
  else
  {restore(i-2); printf("(%d %d) ",i-1,i);}
}

int main(){
    cout << opt() << endl;
    restore(N);
}