uvaoj 12295 - Optimal Symmetric Paths - dblank

uvaoj 12295 - Optimal Symmetric Paths

传送门:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3716

题意:给你一个n*n的矩阵,从[1 1]走到[n n]收集路上的路上的权重,可以走上下左右,但是走的路径必须是关于对角线对称,问你最小的权重和的路径有多少条。

思路:因为啊哟关于对角线对称,那么直接把对称位置的权值加过来,然后从对角线的位置dp过来就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100 + 10, Mod = 1000000009;
typedef long long ll;
int dpN, aN;
int main()
{
    //freopen("D:\input.txt", "r", stdin);
    // freopen("D:\output.txt", "w", stdout);
    int n;
    while(~scanf("%d", &n) && n)
    {
        for(int i = 1; i<=n; i++)
            for(int j = 1; j<=n; j++)
                scanf("%d", &ai);
        for(int i = 1; i<n; i++)
            for(int j = 1; i+j<=n; j++)
                ai += an+1-j;
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i<=n; i++)
            dpi = 1;
        for(int k = n; k>=2; k--)
        {
            for(int i = k-1; i>=1; i--)
            {
                int j = k - i;
                if(ai == ai+1)
                    dpi = (dpi+1 + dpi)%Mod, ai += ai+1;
                if(ai > ai+1)
                    dpi = dpi+1 , ai += ai+1;
                if(ai < ai+1)
                    dpi = dpi, ai += ai;
            }
        }
        printf("%dn", a1);
    }
    return 0;
}

 

相关文章

发表新评论