哔！數字三角形全體集合！
數字三角形！到！
數字三角形W！到！
數字三角形WW！到！
數字三角形WWW！到！
--------------------------------------------------------------------------------------------------------------------------------------------------------
數字三角形，一個灰常灰常典型的動規題，是一道灰常灰常水的動規題，
時間限制: 1 s 空間限制: 128000 KB 題目等級 : 黃金 Gold 題目描述 Description
如圖所示的數字三角形，從頂部出發，在每一結點可以選擇向左走或得向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。
輸入描述 Input Description
第一行是數塔層數N(1<=N<=100)。
第二行起，按數塔圖形，有一個或多個的整數，表示該層節點的值，共有N行。
輸出描述 Output Description輸出最大值。
樣例輸入 Sample Input5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
樣例輸出 Sample Output86
話不多說上代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[110][110]={0},n;
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
cin>>a[i][j];
for (int i=n-1;i>=1;--i)
for (int j=1;j<=i;j++)
a[i][j]=max(a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]);
cout<<a[1][1];
return 0;
}
--------------------------------------------------------------------------------------------------------------------------------------------------------
重點說的是後三個轉換型的題，我們先跳過 數字三角形W ，先來看數字三角形WW和WWW；
其實這兩道題也是水題，先看題目：
時間限制: 1 s 空間限制: 32000 KB 題目等級 : 鑽石 Diamond 題目描述 Description
數字三角形必須經過某一個點，使之走的路程和最大
輸入描述 Input Description第1行n，表示n行
第2到n+1行為每個的權值
程序必須經過n div 2,n div 2這個點
最大值
樣例輸入 Sample Input2
1
1 1
2
數據范圍及提示 Data Size & Hintn <=25
要求必須經過（n/2，n/2）這個點的話，那我們只需把這個點的值先加上一個較大的數，
最後只需給結果減去你給它加上的值就好了，水題直接上代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[110][110]={0},n;
bool f[110][110]={0};
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
{
cin>>a[i][j];
}
a[n/2][n/2]+=5000;
for (int i=n-1;i>=1;--i)
for (int j=1;j<=i;j++)
a[i][j]=max(a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]);
cout<<a[1][1]-5000;
return 0;
}
--------------------------------------------------------------------------------------------------------------------------------------------------------
時間限制: 1 s 空間限制: 32000 KB 題目等級 : 鑽石 Diamond 題目描述 Description
數字三角形必須經過某一個點，使之走的路程和最大
輸入描述 Input Description第1行n，表示n行
第2到n+1行為每個的權值
第n+2行為兩個數x,y表示必須經過的點
最大值
樣例輸入 Sample Input2
1
1 1
1 1
2
數據范圍及提示 Data Size & Hintn<=25
這題思路與WW一樣一樣滴，只是把必走的點變成了（x，y），
上代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[110][110]={0},n,x,y;
bool f[110][110]={0};
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
cin>>a[i][j];
cin>>x>>y;
a[x][y]+=5000;
for (int i=n-1;i>=1;--i)
for (int j=1;j<=i;j++)
a[i][j]=max(a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]);
cout<<a[1][1]-5000;
return 0;
}
--------------------------------------------------------------------------------------------------------------------------------------------------------
到了最重點的題：數字三角形W，這個題一開始我並沒有想出較簡單做法，後來敬愛的學哥學姐教會了我，因為畢竟我也是個蒟蒻啊...具體做法在代碼中解釋吧。
時間限制: 1 s 空間限制: 32000 KB 題目等級 : 黃金 Gold 題目描述 Description
數字三角形
要求走到最後mod 100最大
第1行n，表示n行
第2到n+1行為每個的權值
mod 100最大值
樣例輸入 Sample Input2
1
99 98
99
數據范圍及提示 Data Size & Hintn<=25
代碼：
//我是用的倒推的思路做的，順推其實思路一樣，轉換一下就好，這裡只給出倒推得代碼
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[26][26]={0};
bool f[26][26][100]={0};
int main()
{
cin>>n;
for (int i=1;i<=n;i++) //數據的讀入
for (int j=1;j<=i;j++)
cin>>a[i][j];
for (int i=1;i<=n;i++) //這一步的代碼是為了將最後一排的所有數存下來
f[n][i][a[n][i]]=true;
for (int i=n-1;i>=1;--i) //這裡是主要過程，思路：將所有的可能性mod100都存下來，
for (int j=1;j<=i;j++)
for (int k=0;k<=99;k++)
{
if (f[i+1][j][k])
f[i][j][(k+a[i][j])%100]=true;
if (f[i+1][j+1][k])
f[i][j][(k+a[i][j])%100]=true;
}
for (int k=99;k>=0;--k) //找出所有可能性中最大的可能，輸出，這個題就AC咯、
if (f[1][1][k])
{
cout<<k;
return 0;
}
}
