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

AOJ再挑戦96～100 - (2014/02/06 (木) 08:24:03) の編集履歴(バックアップ)

---

問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";
    }
}

問97　Sum of Integers II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0097
0～100までの数を同じ数を使わずにｎ個取り出しその和がｓになる組み合わせは何通りあるか？

解法
0を足す場合、１を足す場合、、、100を足す場合と順番に動的計画法で計算すれば解けます。
昔考えたのと全く同じ解法でこれより早いのはちょっと思いつきません。

#include<stdio.h>
#include<string.h>
#include<iostream>

int main(){
	long long int dp[10][1001];
 	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int i=0;i<=100;i++){
		for(int k=9;k>=1;k--){
			for(int j=0;j+i<=1000;j++){
				dp[k][j+i]+=dp[k-1][j];
			}
 		}	
	}
	int n,s;
	while(1){
		scanf("%d %d",&n,&s);
 		if(n==0&&s==0)break;
		std::cout<<dp[n][s]<<"\n";
	}
}