[ブルーブリッジカップ]試験問題Aアルゴリズム訓練切手動的計画問題解とC++サンプルコード

ブルーブリッジカップ試験問題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
考え方:
どうてきけいかくだい

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