[ブルーブリッジカップ]試験問題Aアルゴリズム訓練切手動的計画問題解とC++サンプルコード
14898 ワード
ブルーブリッジカップ試験問題Aアルゴリズム訓練切手
時間制限:1.0 sメモリ制限:512.0 MB問題説明所与の封筒があり、N(1≦N≦100)の位置に切手を貼ることができ、各位置に切手を貼ることができる.私达は今M(M<=100)种类の异なる邮便料金の切手があって、額面はX 1で、X 2....Xm分(Xiは整数、1≦Xi≦255)で、それぞれN枚あります.
明らかに、封筒に貼ることができる郵便料金の最小値はmin(X 1,X 2,...,Xm)、最大値はN*max(X 1,X 2,...,Xm)である.すべての貼り付け法で得られた郵便料金は、1からある値までの連続郵便料金シーケンスが存在するか否かを求め、そのシーケンスの最大値を出力する集合(集合に重複数値がない)を形成することができる.
例えば、N=4、M=2、額面はそれぞれ4点、1点となり、1、2、3、4、5、6、7、8、9、10、12、13、16のシーケンスが形成され、1からの連続郵便シーケンスは1、2、3、4、5、6、8、9、10となるので、連続郵便シーケンスの最大値は10点となる.入力形式第1行:最大貼り付け許可切手枚数N;2行目:切手の種類M;3行目:スペースで区切られたM個の数字で、切手の額面Xiを表します.注意:Xiシーケンスは必ずしもサイズが規則的ではありません!出力フォーマット1からの連続郵便料金シーケンスの最大値MAX.1点からのシーケンス(すなわち入力切手に1点額面の切手がない)が存在しなければ出力.サンプル入力サンプル一:4 2 4 1サンプル二:10 5 2 4 8 10
サンプル出力サンプル1:10サンプル2:0
考え方:
どうてきけいかくだい
(一)記入表
(二)状態遷移方程式:
(三)例を挙げる
(四)上式はコードで表す.
C++サンプルコード:
時間制限:1.0 sメモリ制限:512.0 MB問題説明所与の封筒があり、N(1≦N≦100)の位置に切手を貼ることができ、各位置に切手を貼ることができる.私达は今M(M<=100)种类の异なる邮便料金の切手があって、額面はX 1で、X 2....Xm分(Xiは整数、1≦Xi≦255)で、それぞれN枚あります.
明らかに、封筒に貼ることができる郵便料金の最小値はmin(X 1,X 2,...,Xm)、最大値はN*max(X 1,X 2,...,Xm)である.すべての貼り付け法で得られた郵便料金は、1からある値までの連続郵便料金シーケンスが存在するか否かを求め、そのシーケンスの最大値を出力する集合(集合に重複数値がない)を形成することができる.
例えば、N=4、M=2、額面はそれぞれ4点、1点となり、1、2、3、4、5、6、7、8、9、10、12、13、16のシーケンスが形成され、1からの連続郵便シーケンスは1、2、3、4、5、6、8、9、10となるので、連続郵便シーケンスの最大値は10点となる.入力形式第1行:最大貼り付け許可切手枚数N;2行目:切手の種類M;3行目:スペースで区切られたM個の数字で、切手の額面Xiを表します.注意:Xiシーケンスは必ずしもサイズが規則的ではありません!出力フォーマット1からの連続郵便料金シーケンスの最大値MAX.1点からのシーケンス(すなわち入力切手に1点額面の切手がない)が存在しなければ出力.サンプル入力サンプル一:4 2 4 1サンプル二:10 5 2 4 8 10
サンプル出力サンプル1:10サンプル2:0
考え方:
どうてきけいかくだい
sss:
f[sss]: sss
v[]:
(一)記入表
f[0]=0 f[1]=1 f[2]=2 f[3]=3
f[4]=1 f[5]=2 f[6]=3 f[7]=4
f[8]=2 f[9]=3 f[10]=4 f[11]=5
f[12]=3
(二)状態遷移方程式:
f[sss]=min{
f[sss-v[j]]+1} (0<=j<n,sss>=v[j],f[sss]<=k)
(三)例を挙げる
:
3 :
v[3]={
i,j,k}
f[sss]=min{
f[sss-i]+1,f[sss-j]+1,f[sss-k]+1}//3
4 :
v[4]={
i,j,k,l}
f[sss]=min{
f[sss-i]+1,f[sss-j]+1,f[sss-k]+1,f[sss-l]+1}//4
(四)上式はコードで表す.
v[3]={
a,b,c};
int tempmin= ;
for(i=0;v.size();i++){
tempmin=min(tempmin,f[sss-v[i]]+1);
f[sss]=tempmin;
}
C++サンプルコード:
#include
#include
#define min(A,B) ((A)
using namespace std;
int f[100001]={
0};
int main(){
int N, M;
cin>>N>>M;
int value[N];
for (int i = 0; i < M; i++){
cin>>value[i];
}
int j = 0;
while (f[j] <= N){
// N,
j++;
int m = 4000000;
for (int i = 0; i < M; i++){
if (j >= value[i]){
// >=value[i], f[j-value[i]]
m = min(m, f[j - value[i]] + 1);// -
f[j] = m;
}
}
if(f[j]==0){
//
break;
}
}
cout<<j - 1;
return 0;
}