洛谷P 118デジタル三角形の問題解

タイトル
この問題は私たちは一見よく知っている.DPでできる問題だと思います.しかし、目を通すと、間違っていることに気づきます.その問題は順押しだから、この問題は逆押しだ.
こうなったらどうしよう.
原稿用紙に押してもいいです.勝手に数nを書きます.
さらにa,b,c,dと表記します.
n=4の場合
次の式を得ることができます
           sum=a+3b+3c+d
           a+2b+c         b+2c+d
         a+b          b+c         c+d 
    a            b              c           d
だから私たちは楊輝三角を考えることができます.
yh配列を楊輝三角とした.
まず,楊輝三角の値を前処理し,主関数でもある.

int main()
{
    cin>>n>>sum; 
    yh[1][1]=1; 
    for(int i=2;i<=n;i++) 
        for(int j=1;j<=i;j++) 
            yh[i][j]=yh[i-1][j-1]+yh[i-1][j]; 
    dfs(1,0); 
    return 0; 
}

再検索
検索関数:dfs(step,sum)
Stepは今からいくつかの数を選び、sumは今選んだ数の和を指します.
次にdfsを書きます.
私たちは2つの判断を加えて退出するかどうかを判断することができます.
一つは,シナリオが出力されたか否かを判断することである.
1つは、現在の値がsumより大きいかどうかです.
合計n個の数があり、このn個の数は1からnまでの配列であるからである.
したがって,1からnまで列挙することができ,この数が使用されなければsumに楊輝三角を乗じた値を加えることができる.
次に、上記の2つの判断を使用して、終了しない場合は、終了または結果が見つかるまで続行します.
コード:

#include
using namespace std;
int n,sum,yh[20][20],a[14]; 
bool flag,vis[14];
void dfs(int step,int s)
{
    if(flag)
        return;
    if(s>sum)
        return;
    if(step==n+1) 
    {
        if(s==sum)
        {
            for(int i=1;i<=n;i++)
                cout<' ';
flag=true; 
}
return; 
}
for(int i=1;i<=n;i++)
if(!vis[i])
{
a[step]=i;
s+=yh[n][step]*a[step]; 
vis[i]=true; 
dfs(step+1,s); 
vis[i]=false;
s-=yh[n][step]*a[step]; 
}
}
int main()
{
cin>>n>>sum; 
yh[1][1]=1; 
for(int i=2;i<=n;i++) 
for(int j=1;j<=i;j++) 
yh[i][j]=yh[i-1][j-1]+yh[i-1][j]; 
dfs(1,0); 
return 0; 
}

 
転載先:https://www.cnblogs.com/liuwenyao/p/9216824.html