Suntuubi-palvelussa käytetään evästeitä. Palvelua käyttämällä hyväksyt evästeiden käytön. Lue lisää. OK

#include <fstream>
#include <vector>
using namespace std;

// Datatähti 2009 - Task 1 - Version 2
//
// Dynamic programming solution with O(n,m) = n*m
//
// Note: Faster than brute force solution in larger cases
//
// Source by Gorath
//
int main() {
    int m,n,i,j,result=0;
    vector<int> coders;
    vector<vector<int> > dp;
    ifstream in("hissi.in");
    ofstream out("hissi.out");
   
    // Lue tiedot
    in >> m >> n;
    coders.resize(n);
    for (i=0;i<n;i++) in >> coders[i];

    // Algoritmi
    dp.push_back(vector<int>(m+1,0));
    dp[0][0]=1;
    for (i=0;i<n;i++) {
        dp.push_back(vector<int>(m+1,0));
        for (j=0;j<m+1;j++)
            if (dp[i][j]) {
                dp[i+1][j] += dp[i][j];
                if (j+coders[i]<=m) dp[i+1][j+coders[i]] += dp[i][j];
            }
    }
    for (i=0;i<m+1;i++) result+=dp[n][i];

    // Kirjoita vastaus ja sulje tiedostot
    out << result;
    in.close();
    out.close();

    return 0;
}


©2019 layout9 - suntuubi.com