쌍선dp-목장물어

목장
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit 
Status 
Practice 
FZU 2234
Description
샤오차 학생은 목장 물담을 하고 있다.이 게임의 지도는 가장자리 길이가 n인 정사각형으로 볼 수 있다.
샤오차 학생은 갑자기 심혈을 기울여 나무를 베러 가려고 했지만, 도끼는 샤오차의 오른쪽 아래에 있었다.
샤오차는 효율을 중시하는 사람이기 때문에 가장 짧은 노정으로 오른쪽 하단까지 갔다가 다시 왼쪽 상단으로 돌아간다.그리고 길에서 꽃, 돈, 똥 등 물건을 주우거나 밟는다.
아이템은 최대 한 번만 수령할 수 있습니다.어떤 칸에 있을 때 칸에 물건이 더 있으면 반드시 가져가야 한다.시작점과 끝점에 물건이 있을 수도 있다.
모든 물품에 대해 우리는 가치를 정의할 것이다. 물론 왕복 후에 우리가 얻는 물품의 가치는 크면 클수록 좋다.하지만 샤오차 학생은 열심히 게임을 하고 있으니 가장 큰 가치와 가치를 계산해 보세요.
Input
EOF에 대한 다중 데이터 그룹(<=10)
첫 번째 행은 사각형의 크기를 나타내는 양의 정수 N(N≤100)을 입력합니다.
다음은 총 N행, 매 행마다 N개의 정수 Ai, j(|Ai, j|≤10^9)로 해당 위치에 있는 물품의 가치를 나타낸다.값이 0이면 아이템이 없음을 의미합니다.
Output
각 그룹의 데이터는 최대 가치 및 를 나타내는 정수를 출력합니다.
Sample Input
211 1416 12
Sample Output
53

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
using namespace std;
ll v[110][110],f[210][110][110];
int main()
{
    int t,n,m,c;
    int i,j,k;
    while(scanf("%d",&n)!=EOF){
        c=n+n-1;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                scanf("%I64d",&v[i][j]);
        memset(f,-0x3f3f3f3f,sizeof(f));
        f[1][1][1]=v[1][1];
        for(k=2;k<=c;k++) {
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                if(i!=j)
                    f[k][i][j]=max(max(f[k-1][i-1][j],f[k-1][i][j-1]),max(f[k-1][i][j],f[k-1][i-1][j-1]))+
                    v[i][k-i+1]+v[j][k-j+1];
        		else
        			f[k][i][j]=max(max(f[k-1][i-1][j],f[k-1][i][j-1]),max(f[k-1][i][j],f[k-1][i-1][j-1]))+
        			v[i][k-i+1];
		}
        printf("%I64d
",f[c][n][n]);
    }
    return 0;
}