堆石子

link: 堆石子
Description:
JQM开始玩堆石子的游戏。有 m 颗质量大小不同的石子，从最下面一层开始堆石子，最下面一层放置 n 颗石子，每层减少一颗石子，恰好到最上一层为 一颗 石子。现在从最下面一层开始每层石子中取出一颗石子（注意，为了方便取出，要求只能拿和已拿石子相邻的两颗石子中的一颗），求能取出的石子质量和最大为多少？

Input
石子总数 m(1≤m≤400)
接下来每行表示从最下面一层开始每层每个石子的质量 w(1≤w≤1e8)

Output
能取出的最大石子质量和

Examples
input
6
1 4 6
3 2
1
output
9
Note
1
2 3
4 5 6
7 8 9 10
如果你拿了8，那么你就只能拿4或者5而不能拿6

Intentional analysis:
What we should is find the "State transition equation".We know that the value of the optimal solution in the bottom row is his own, which is the critical condition.Another part of the state transition equation is that the value of the optimal solution is the maximum of the number above it and the number in the upper right corner, and then adds itself.Of course,we can solve this problem with DFS.Memory search is a perfect way to avoid TLE.
So,we can get the "State transition equation":

dp[i][j] = a[i][j]     if(i==n)
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j]

n represents the number of rows of triangles.
a[i][j] represents the value of the i-th row and the j-th column in the triangle.
dp[i][j] represents the value of the optimal solution for this position.
Click to see Chinese Intentional analysis 这是一道DP的裸题，我们需要的就是推出递推公式就行了。首先我们知道若想得到当前位置的最优解，就需要知道它上一个位置的最优解，一开始可能会想到dfs，看一下数据范围，dfs的话肯定会超时，但是dfs也是可以做的，但是需要用到记忆化搜索。继续说回我们用DP做的方法，我们知道最下面那一行的最优解的值就是他自己，这就是临界条件，状态转移方程的另一部分就是这个数最优解的值就是它的上面的那个数和右上角的那个数的最大值加上自己本身。所以我们可以得到 ``` dp[i][j] = a[i][j] if(i==n) dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j] n代表的是三角形的行数。 a[i][j]代表的是三角形中的第i行第j列的值。 dp[i][j]代表的就是这个位置的最优解的值。 ```

Code-dp:

#include<bits/stdc++.h>
using namespace std;
const int maxn=400;
typedef long long ll;
ll a[maxn][maxn];
ll dp[maxn][maxn];
int main()
{
    ll n,k=1;
    cin>>n;
    while(n)
    {
        n-=k;
        k++;
    }
    k-=1;
    for(ll i=k;i>=1;i--)
        for(ll j=1;j<=i;j++)
        cin>>a[i][j];

    for(ll i=k;i>=1;i--)
    {
        for(ll j=1;j<=i;j++)
            if(i==k)    dp[i][j]=a[i][j];
            else dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
    }
    cout<<dp[1][1]<<endl;
    return 0;
}

Code-dfs:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000;
ll a[maxn][maxn];
ll dp[maxn][maxn];
ll n,k=1;
ll dfs(ll x,ll y)
{
    if(dp[x][y])    return dp[x][y];
    if(x==k) return dp[x][y]=a[x][y];
    ll m = dfs(x+1,y);
    ll n = dfs(x+1,y+1);
    return dp[x][y]=max(m,n)+a[x][y];
}
int main()
{
    cin>>n;
    while(n)
    {
        n-=k;
        k++;
    }
    k-=1;
    for(ll i=k;i>=1;i--)
        for(ll j=1;j<=i;j++)
        cin>>a[i][j];
    cout<<dfs(1,1)<<endl;
    return 0;
}

If you still confused with dp,just think about Fibonacci sequence.

F[0]=1
F[1]=1
F[2]=2
F[3]=3
F[4]=5
......
F[n]=F[n-1]+F[n-2]

F[n]=F[n-1]+F[n-2] is Fibo's "State transition equation".

赏