codeforces 82D Two out of Three

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
typedef long long lld;
const int oo=0x3f3f3f3f;
const lld OO=1LL<<61;
const int MOD=1000000007;
int dp[1005][1005];
int a[1005];
int n;

int dfs(int i,int j)
{
    if(dp[i][j]!=-1)return dp[i][j];
    if(j>n)return dp[i][j]=a[i];
    if(j==n)return dp[i][j]=max(a[i],a[j]);
    dp[i][j]=max(a[i],a[j])+dfs(j+1,j+2);
    dp[i][j]=min(dp[i][j],max(a[i],a[j+1])+dfs(j,j+2));
    dp[i][j]=min(dp[i][j],max(a[j],a[j+1])+dfs(i,j+2));
    return dp[i][j];
}

void output(int i,int j)
{
    if(j>n)
    {
        printf("%d
",i);
    }
    else if(j==n)
    {
        printf("%d %d
",i,j);
    }
    else if(dp[i][j]==max(a[i],a[j])+dp[j+1][j+2])
    {
        printf("%d %d
",i,j);
        output(j+1,j+2);
    }
    else if(dp[i][j]==max(a[i],a[j+1])+dp[j][j+2])
    {
        printf("%d %d
",i,j+1);
        output(j,j+2);
    }
    else if(dp[i][j]==max(a[j],a[j+1])+dp[i][j+2])
    {
        printf("%d %d
",j,j+1);
        output(i,j+2);
    }
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,-1,sizeof dp);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        printf("%d
",dfs(1,2));
        output(1,2);
    }
    return 0;
}
/**
4
1 2 3 4
5
2 4 3 1 4


*/