1

私はこの問題を解決していました-> http://www.spoj.com/problems/SAMER08F/ (非常に単純な問題) ... 最初に AC を取得しました... 私の解決策は次のようなものでした (かなり単純明快です) :

#include<iostream>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
    while(n!=0)
    {
    printf("%d",((n)*(n+1)*((2*n)+1))/6);
    printf("\n");
    scanf("%d",&n);
    }
    return 0;
}

私はこのリストhttp://ahmed-aly.com/Category.jsp?ID=33を調べていて、ファインマンがDPの問題としてリストされているのを見つけました...私はDPの初心者で、この問題がどのように構成されているのかわかりませんサブ問題の。再帰関係を見つけるためのヘルプやヒントは非常に役立ちます。

4

2 に答える 2

1

それはただのばかげたDPです。
あなたがここでしていることは   方式 正しいですか？
代わりに、平方和を保持する配列を作成することができます (sumSquares と呼びましょう)。さて、これは配列を埋める方法です：

  1. sumSquares[0] = 0; (基本ケース、最初のゼロ要素の二乗和はゼロです)。

  2. sumSquares[i] = sumSquares[i - 1] + 方式( i要素の平方和は(i - 1)要素の平方和 + i 番目の 要素の平方和)

以上です！n まで反復すると、答えが sumSquares[n] に保存されます。

于 2013-08-08T06:19:38.327 に答える