bool cmp(int a,int b)
{
return a > b;
}
int func2(vector<int> &g, int m, int n)
{
if (g.size() != n)return -1;
sort(g.begin(), g.end(), cmp);
vector<vector<int>> dp(10, vector<int>(20, INT_MAX));
dp[0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (j < i)continue;
dp[i][j] = min(dp[i][j], dp[i][j - i]);
for (int k = 0; k < i; k++)
{
int value = 0;
for (int p = k + 1; p <= i; p++){
value += k*g[p-1];
}
dp[i][j] = min(dp[i][j], dp[k][j - i + k] + value);
}
}
}
return dp[n][m];
}
int main()
{
vector<int> g = { 3,1,2,4,5 };
int res = func2(g, 8,5);
cout << res << endl;
system("pause");
}
|
