完璧な未来の星のプログラミング試合の再試合の第2試合はアクティブコードを配布します
1331 ワード
タイトルの説明
重複しない数値のセットからランダムないくつかの数値組成検証コードが得られ、これらの数値が加算され、同じである限り、同じ検証コードのセットとみなされ、最後に、有効検証コードのセットが合計でどれだけ得られるかが望ましい.
次に、Nの異なる数のセットから、Cのグループの個数を取得することが望ましい.組み合わせの個数は1個である可能性がありN個である可能性がある.
入力フォーマット
1行目は、合計データ群数を表す整数Mを1つ入力します.
2行目に1個の整数23行目は1つの整数Cを入力し、数字の和を表す
4行目はN個の異なる数字(数字＞0)を入力し、中間はカンマで区切られ、0<単一数字<=100
テストフォーマット
とresultの認証コードの合計数に従います.
サンプルを入力:
2
4
3
11 ,2, 3, 1
3
3
1,2,3
出力サンプル
2
2
動的計画を用いて、01リュックサックの思想に変換することができ、状態方程式:dp[j]=dp[j]+dp[j-num[i];ここでnum[i]はi番目の数値を表し、dp[j]は、jのシナリオ数として定義される.
重複しない数値のセットからランダムないくつかの数値組成検証コードが得られ、これらの数値が加算され、同じである限り、同じ検証コードのセットとみなされ、最後に、有効検証コードのセットが合計でどれだけ得られるかが望ましい.
次に、Nの異なる数のセットから、Cのグループの個数を取得することが望ましい.組み合わせの個数は1個である可能性がありN個である可能性がある.
入力フォーマット
1行目は、合計データ群数を表す整数Mを1つ入力します.
2行目に1個の整数2
4行目はN個の異なる数字(数字＞0)を入力し、中間はカンマで区切られ、0<単一数字<=100
テストフォーマット
とresultの認証コードの合計数に従います.
サンプルを入力:
2
4
3
11 ,2, 3, 1
3
3
1,2,3
出力サンプル
2
2
動的計画を用いて、01リュックサックの思想に変換することができ、状態方程式:dp[j]=dp[j]+dp[j-num[i];ここでnum[i]はi番目の数値を表し、dp[j]は、jのシナリオ数として定義される.
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
int num[110];
int dp[110];
int main()
{
int m;
cin>>m;
while(m--)
{
int n;
cin>>n;
int c;
cin>>c;
for(int i=1;i<=n;i++)
{
cin>>num[i];
if(i!=n)cin.get();
}
sort(num+1,num+n+1);
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=c;j>=num[i];j--)
{
dp[j]=dp[j]+dp[j-num[i]];
}
}
cout<<dp[c]<<endl;
}
}