UVA 10564_ Paths through the Hourglass

제목:

0-9의 숫자로 모래시계처럼 생긴 도형을 구성하는데 첫 줄부터 왼쪽 아래나 오른쪽 아래를 따라 마지막 줄에 도착해야 한다. 몇 가지 다른 경로가 있는지 물어보고 마지막 경로의 정수를 주어진 숫자로 합쳐야 한다.

분석:

간단한 계수 dp, 마지막 줄부터 dp[i][j][k]를 설정하여 아래에서 위로 i줄을 지나 j열에 이르게 한다. 이때 경로의 정수의 합은 k의 경로 종수이다.역귀환 방정식 가져오기:

dp[i][j][k] += dp[i-1][j][k-a[i][j]] +dp[i-1][j + 1][k-a[i][j]];

마지막으로 dfs 출력 경로, 여러 경로를 주의할 때 좌표 사전의 순서를 최소화해야 합니다!

코드:

#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
const int maxn =100, INF =0x3fffffff;
int a[maxn][maxn];
long long dp[maxn][maxn][550];
int n, p;
void dfs(int i, int j, int t)
{
  if(i == 2*n-1) return;
  int temp;
  if(i < n){
    if(j>1&&dp[2*n-i-1][j-1][t-a[i][j]]){
        cout<<'L';
        temp = j-1;
    }else{
        cout<<'R';
        temp = j;
    }
    dfs(i+1,temp,t-a[i][j]);
 }else {
        if(dp[2*n-i-1][j][t-a[i][j]]){
            cout<<'L';
            temp = j;
        }else{
            cout<<'R';
            temp = j + 1;
        }
         dfs(i+1,temp,t-a[i][j]);
    }

    return;
}
int main (void)
{
    while(cin>>n>>p && n||p){
    for(int i = 1; i <= n; i++)
        for (int j = 1; j <=n-i+1; j++)
            cin>>a[i][j];

    for(int i = n + 1; i < 2 * n; i++)
        for (int j = 1; j <= i - n + 1; j++)
            cin>>a[i][j];

    memset(dp,0,sizeof(dp));

    for(int i =  2 * n - 1; i >= n; i--)
        for(int j = 1; j <= i - n+1; j++)
            for(int k = a[i][j]; k <= p; k++){
                if(i==2*n-1 && k==a[i][j]) dp[1][j][k]=1;
                else  dp[2*n- i][j][k] += dp[2*n-i-1][j][k-a[i][j]] +dp[2*n-i-1][j + 1][k-a[i][j]];
            }

     for(int i = n-1; i > 0; i--){
        for(int j = 1; j <= n - i + 1; j++){
         for(int k = a[i][j]; k <= p; k++){
            if(j > 1)  dp[2*n - i][j][k] += dp[2*n-i-1][j - 1][k-a[i][j]];
            if(j < n-i+1)  dp[2*n- i][j][k] += dp[2*n-i-1][j][k-a[i][j]];
         }
        }
     }
    long long total = 0;
    int s;
    for(int i = n; i >= 1; i--){
        if(dp[2*n-1][i][p]>0){
                total += dp[2*n-1][i][p];
                s = i;
            }
        }
    if(total == 0) cout<<0<<endl<<endl;
    else{
        cout<<total<<endl;
        cout<<s-1<<' ';
        dfs(1,s,p);
        cout<<endl;
    }
}
    return 0;
}

4

자세하게 문제를 심사한다!!!주제를 읽는 데 너무 경솔해서 한 번도 주제의 뜻을 함정에 빠뜨린 적이 없다

4

디버깅 시간이 비교적 길고 사고방식이 간단명료하며 코드를 쓸 때 세부적인 오류를 최대한 피한다