BOJ7579-app

タイムアウトメモリ制限正解の送信正解正解正解正解率1秒128 MB 101443610260337.223%

質問する

私たちはスマートフォンを使っていろいろなアプリケーションを実行しています.ほとんどの場合、画面に表示される「実行中」のアプリケーションは1つしかありませんが、見えない場合は多くのアプリケーションが「アクティブ」になります.アプリケーションがアクティブ化されるとは、画面に表示されなくてもメインメモリに記録される前の状態です.現在実行されていない場合でも、ユーザーが以前実行していたアプリケーションを再ロードすると、メインメモリから以前のステータスが読み込まれ、実行準備が迅速に完了するため、メモリに残っています.
しかし、スマートフォンのメモリは限られているため、実行したすべてのアプリケーションをアクティブにしてメインメモリに残すだけで、メモリ不足が発生しやすい.新しいアプリケーションを実行するために必要なメモリが不足している場合、スマートフォンのオペレーティングシステムはアクティブなアプリケーションからいくつか選択し、メモリから削除するしかありません.このプロシージャをアプリケーションの無効化(Disable)と呼びます.
メモリが不足している場合、アクティブなアプリケーションをランダムに必要なメモリに無効にするのは良い方法ではありません.無効なアプリケーションを再実行するには、より多くの時間がかかるためです.これらのアプリケーションの非アクティブ化の問題をスマートに解決するためのプログラムを作成する必要があります.
現在N個のアプリケーションがあり、A 1,...、ANが有効になっているとします.これらのアプリケーションAiが使用するメモリは、それぞれmiバイトである.また,アプリケーションAiを無効にして再実行しようとすると,余分な費用(時間など)をciに量子化する.この場合、ユーザは、新しいアプリケーションBを実行するために、追加のMバイトメモリを必要とする.すなわち、現在アクティブ化されているアプリケーションA 1は…すなわち,より多くのMバイト以上のメモリを得るためにANからいくつか無効にする必要がある.無効化時のコストciの和を最小限に抑えて、必要なメモリMバイトを確保する方法を見つける必要があります.

入力

入力は3行で構成されています.1行目は整数NとMをスペース文字で区切り、2行目と3行目はそれぞれN個の整数をスペース文字で区切ります.2行目のN個の整数は、現在アクティブ化されているapple A 1,...,LANで使用するメモリバイト数m 1,…,mnを表し、3行目の整数は各アプリケーションを無効にするコストc 1,...,cnを表す
しかし、1≦N≦100、1≦M≦1000000、1≦m 1、...mn≤10000000.また、0≦c 1,…,cn≤100,M≤m1+m2+...mnです.

しゅつりょく

必要なメモリMバイトを確保するには、アプリケーションを無効にする最小コストを計算し、ローに出力する必要があります.

に近づく

これはよく出会うギリシャ問題だ.
メモリの範囲が広いため、コストに基づいてテーブルを作成します.
これで、アプリケーションでメモリの最値を発色で更新すればいいようになりました.
その後0から巡回を開始し、1番目のM以上を出力する.

に答える

顔色のコアは後ろから充填されます.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };


int N, M, dp[10001];
pair<int, int> arr[100];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	MS(dp, 0);
	CIN2(N, M);
	FUP(i, 0, N - 1) CIN(arr[i].first);
	FUP(i, 0, N - 1) CIN(arr[i].second);
	sort(arr, arr + N);
	FUP(i, 0, N - 1)
	{
		FDOWN(j, 10000, arr[i].second)
		{
			dp[j] = max(dp[j], dp[j - arr[i].second] + arr[i].first);
		}
	}
	FUP(i, 0, 10000)
	{
		if (dp[i] >= M)
		{
			COUT(i);
			break;
		}
	}


	return 0;
}