「AOJ再挑戦96～100」の編集履歴（バックアップ）一覧に戻る

AOJ再挑戦96～100 - (2014/02/06 (木) 04:55:29) のソース

*問96　Sum of 4 Integers II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0096
a+b+c+d=n nは4000以下の自然数 a,b,c,dは0～1000までの数で数ｎを作る方法は何通りあるか？

解法
昔の自分のほうがかしこいコードを書いてたのでこちらを掲載。
今書いてみたほうは、計算量800万回。
それに対してこちらの計算量は１万回。
昔のほうが賢いコード書いてるな私。
aで作れる数は0～1000までが一通り。
それにｂを足すと1000～2000までの数が作れてその通りをab[n]とする。
a+b+c=n3としてn3はn3-1000～n3までのab[n3-1000～n3]までの和となる。
ｄを足しても同様。


 #include<stdio.h>
 #include<iostream>
 #include<string.h>
 long long int memo[4001]={0};
 void calc(int up){
    long long int sum=0;
    long long int next[4001]={0};
    for(int i=0;i<=up;i++){
        sum+=memo[i];
        if(i>1000){
            sum-=memo[i-1001];
        }
        next[i]=sum;
    }
    memcpy(memo,next,sizeof(next)); 
 }
  
 int main(){
    for(int i=0;i<=1000;i++)memo[i]=1;//aを決定
    calc(2000);
    calc(3000);
    calc(4000);
    int n;
    while(scanf("%d",&n)!=EOF){
        std::cout<<memo[n]<<"\n";
     }
 }