51 nod 1455宝石ハンター(dp or記憶化検索)

3322 ワード

ソセック島は30001個の島を持つ諸島で、これらの島は直線に沿って均一に間隔を置いて分布し、西から東にかけて0から30000個の島がある.周知のように、これらの島には多くの宝石があり、ソセック島には全部でn個の宝石があり、i番目の宝石は島piに位置している.
小法はちょうど0番の島に着いて、彼は卓越したジャンプ能力を持っていて、以下の規則によって島の間で東にジャンプを繰り返すことができます.
・まず、彼は0番島からd番島に飛び込む
・その後、Lは前回のジャンプの長さであり、すなわち、前回のジャンプが島prev島curであれば、L=cur−prevである.彼は東へL-1、LまたはL+1の長さのジャンプをすることができます.すなわち、島(cur+L-1)、(cur+L)または(cur+L+1)(これらの島が存在する場合)にジャンプします.1回のジャンプの長さは正数でなければなりません.すなわち、L=1の場合、長さ0のジャンプは1回もできません.有効な目的地がなければ、ジャンプを停止します.
小法はジャンプ中に集めた島の宝石を集めます.私たちは小さな方法で収集できる宝石の最大数を見つけなければなりません.
サンプル解釈:最初のサンプルでは、0→10(+1宝石)→19→27(+2宝石)→...
Input

                 n d (1 ≤ n, d ≤ 30000)，                         。
   n          ， i (1 ≤ i ≤ n)     pi(d ≤ p1 ≤ p2 ≤ 
... ≤ pn ≤ 30000)，     i         。

Output

Input例

Outputの例

System Message
(タイトルプロバイダ)
実際にはdp[i][j]でi歩まで歩くことがj歩にまたがる最大獲得量であることは容易に考えられるが、こんなに大きな配列は開けられないに違いない.i番目の島まで歩くとd+jステップにまたがる最大獲得であることをdp{i][j]で表すことができ、最大30000個であるため、このオフセットの最大範囲は約-245~245であり、オフセット量はすべて250を加え、正数オフセット量を得ると、dp[30000][500]を開くと状態を表すことができ、算出された場合、250の修正を減らすことに注意する.
dpコード:

#include
#include
#include
#include
#include
#include
#include
#include
#pragma comment(linker, "/STACK:10240000,10240000")
using namespace std;
typedef long long ll;
const int inf =0x3f3f3f3f;
const double  pi = acos(-1.0);
const int N = 1e5 + 10;
int dp[30300][550], vis[30300];
int main()
{
    int n, d;
    while(cin>>n>>d)
    {
        memset(dp, -1, sizeof(dp));
        memset(vis, 0, sizeof(vis));
        int x, ans = 0;
        for(int i = 0; i=1 && j+d&&Next<=30000 && Next - i>1)
                {
                    dp[Next-1][j-1] = max(dp[Next-1][j-1], dp[i][j]+vis[Next-1]);
                    ans = max(ans, dp[Next-1][j-1]);
                }
            }
        }
        cout<

メモリ検索コード:

#include
#include
#include
#include
#include
#include
#include
#include
#pragma comment(linker, "/STACK:10240000,10240000")
using namespace std;
typedef long long ll;
const int inf =0x3f3f3f3f;
const double  pi = acos(-1.0);
const int N = 1e5 + 10;
int dp[30300][550], vis[30300];
int d;
int dfs(int now, int p)
{
    if(now>30000)
        return 0;
    if(dp[now][p]!=-1)
        return dp[now][p];
    int tmp = 0;
    dp[now][p] = vis[now];
    tmp = max(tmp, dfs(now + p-250+d + 1, p+1));
    if(p+d-250>1)
        tmp = max(tmp, dfs(now + p -250-1+d,p-1));
    tmp = max(tmp, dfs(now + p-250+d, p));
    dp[now][p] += tmp;
    return dp[now][p];

}
int main()
{
    int n;
    while(cin>>n>>d)
    {
        memset(dp, -1, sizeof(dp));
        memset(vis, 0, sizeof(vis));
        int x, ans = 0;
        for(int i = 0; i

oscp——htb——Bank

CakePHP3のルーティングでactionの引数の順番を指定する