牛客-ショッピング
3520 ワード
タイトルの説明:
遠い東方に、キャンディ専門店があります.このキャンディ店では毎日いくつかのキャンディを販売し、毎日m個のキャンディを生産し、i日目のj個目のキャンディの価格はC[i][j]元である.今のあなたは次のn日にキャンディ屋に行って購入したいと思っています.毎日複数のキャンディを買うことができます.キャンディを買わないこともできますが、最大m個を買うことができます.(せいぜいm個しか生産していないので)キャンディを買ってきたら、キャンディを食べるか、残してから食べるかを選ぶことができます.キャンディは期限切れにならないので、このn日間で毎日少なくとも1つのキャンディを食べることができることを保証する必要があります.この店のボスはあなたがよくこの店に行くのを見て、あまり怒っていません.(彼はよく眠れないので)彼は追加でお金を払うように要求します.具体的には、ある日k個のキャンディを購入した場合、この日に追加で(k^2)の費用を支払う必要があります.では、問題が来て、あなたは少なくともいくらで自分の目的を達成することができますか?
説明を入力:
1行目の2つの正の整数nとmは、それぞれ日数とキャンディ店が毎日生産するキャンディの数を表す.次にn行目(2行目からn+1行目)は、1行m個の正の整数であり、x+1行目のy個目の正の整数は、x日目のy個目のキャンディの費用を表す.
出力の説明:
出力には正の整数が1つしかありません.支払いが必要な最小費用を示します.
例1:
入力:
3 2 1 1 100 100 10000 10000
出力:
107
例2:
入力:
5 5 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4
しゅつりょく
10
備考:100%のデータに対して、1≦n、m≦300で、すべての入力数は≦(10^6)である.
考え方1:まず、この問題には毎日k^2の追加費用がかかるところがあります.だから、まずこれを処理して、すべての場所を処理して、毎日の価格をソートして、小さいから大きいまで、キャンディの価格ごとに1、3、5...、k^2が先頭項1であるため,差が2の等差数列の前のn項和を列挙し,次に優先キュー処理すればよい.費用の価値を最小限に抑えるためには、n個のキャンディだけを購入しなければならない.注意:タイトルには「このn日間、毎日少なくとも1つのキャンディを食べることができることを保証する必要があります」という要求があります.したがって、すべてのキャンディの価値をすべてキューに格納してから、最初のn個の価値が最も小さいキャンディを取るべきではありません.n日間の毎日が現在のメンテナンスの列の中で最も価値のあるキャンディを取り出すべきです.参照コードは次のとおりです.
構想2(dp):dp[i][j]:i日目に合計j個のキャンディを買う最低価格を表すと、dp[i][j]=min(dp[i][j],dp[i-1][k]+sum[i][j-k]+(j-k)*(j-k);コードは次のとおりです.
遠い東方に、キャンディ専門店があります.このキャンディ店では毎日いくつかのキャンディを販売し、毎日m個のキャンディを生産し、i日目のj個目のキャンディの価格はC[i][j]元である.今のあなたは次のn日にキャンディ屋に行って購入したいと思っています.毎日複数のキャンディを買うことができます.キャンディを買わないこともできますが、最大m個を買うことができます.(せいぜいm個しか生産していないので)キャンディを買ってきたら、キャンディを食べるか、残してから食べるかを選ぶことができます.キャンディは期限切れにならないので、このn日間で毎日少なくとも1つのキャンディを食べることができることを保証する必要があります.この店のボスはあなたがよくこの店に行くのを見て、あまり怒っていません.(彼はよく眠れないので)彼は追加でお金を払うように要求します.具体的には、ある日k個のキャンディを購入した場合、この日に追加で(k^2)の費用を支払う必要があります.では、問題が来て、あなたは少なくともいくらで自分の目的を達成することができますか?
説明を入力:
1行目の2つの正の整数nとmは、それぞれ日数とキャンディ店が毎日生産するキャンディの数を表す.次にn行目(2行目からn+1行目)は、1行m個の正の整数であり、x+1行目のy個目の正の整数は、x日目のy個目のキャンディの費用を表す.
出力の説明:
出力には正の整数が1つしかありません.支払いが必要な最小費用を示します.
例1:
入力:
3 2 1 1 100 100 10000 10000
出力:
107
例2:
入力:
5 5 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4
しゅつりょく
10
備考:100%のデータに対して、1≦n、m≦300で、すべての入力数は≦(10^6)である.
考え方1:まず、この問題には毎日k^2の追加費用がかかるところがあります.だから、まずこれを処理して、すべての場所を処理して、毎日の価格をソートして、小さいから大きいまで、キャンディの価格ごとに1、3、5...、k^2が先頭項1であるため,差が2の等差数列の前のn項和を列挙し,次に優先キュー処理すればよい.費用の価値を最小限に抑えるためには、n個のキャンディだけを購入しなければならない.注意:タイトルには「このn日間、毎日少なくとも1つのキャンディを食べることができることを保証する必要があります」という要求があります.したがって、すべてのキャンディの価値をすべてキューに格納してから、最初のn個の価値が最も小さいキャンディを取るべきではありません.n日間の毎日が現在のメンテナンスの列の中で最も価値のあるキャンディを取り出すべきです.参照コードは次のとおりです.
#include
#include
#include
using namespace std;
priority_queue, greater>q;
int C[303][303];
int n, m;
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
cin >> C[i][j];
}
sort(C[i] + 1, C[i] + m + 1);
}
for (int i = 1;i <= n;i++)
{
int cnt = 1;
for (int j = 1;j <= m;j++)
{
C[i][j] = C[i][j] + cnt;
cnt += 2;
}
}
long long int res = 0;
for (int j = 1;j <= m;j++)
{
q.push(C[1][j]);
}
res += q.top();
q.pop();
for (int i = 2;i <= n;i++)
{
for (int j = 1;j <= m;j++)
{
q.push(C[i][j]);
}
res += q.top();
q.pop();
}
cout << res << endl;
return 0;
} 構想2(dp):dp[i][j]:i日目に合計j個のキャンディを買う最低価格を表すと、dp[i][j]=min(dp[i][j],dp[i-1][k]+sum[i][j-k]+(j-k)*(j-k);コードは次のとおりです.
#include
#include
#include
using namespace std;
typedef long long int ll;
int C[303][303];
long long int dp[303][303], sum[303][303];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;i++)
for (int j = 1;j <=n;j++)
{
sum[i][j] = 1e9+7;
dp[i][j] = 1e9+7;
}
for (int i = 1;i <= m;i++)
{
for (int j = 1;j <= m;j++)
cin >> C[i][j];
sort(C[i] + 1, C[i] + 1 + m);
for (int j = 1;j <= m;j++)
sum[i][j] = sum[i][j - 1] + C[i][j];
}
for (int j = 1;j <= m;j++)
dp[1][j] = sum[1][j] + j * j;
for(int i=2;i<=n;i++)//
for (int j = i;j <= n;j++)//j i
{
for (int k = i - 1;k <= j;k++)//k i-1
{
if(j-k<=m)
dp[i][j] = min(dp[i][j], dp[i - 1][k] + sum[i][j - k] + (j - k) * (j - k));
}
}
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<