hdu 1257最少ブロックシステム【贪欲𞓜DP——LIS】
10770 ワード
リンク:
http://acm.hdu.edu.cn/showproblem.php?pid=1257
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28195#problem/D
最小ブロックシステム
Time Limit：2000/1000 MS（Java/Others） メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：12863 Acceepted Submission（s）：5100
Problem Description
ある国は、敵国のミサイル攻撃を防ぐために、ミサイル迎撃システムを開発しました。しかし、このミサイル迎撃システムには、第一弾は任意の高度に到達することができますが、その後はどの砲弾も前発の高さを超えてはいけません。ある日、雷達は敵国のミサイル攻撃を捉えました。このシステムはまだ試用段階ですので、システムは一つしかありません。だから全てのミサイルは迎撃できないかもしれない。
どうすればいいですかもっとシステムを作ればいいです。簡単ですが、コストはどうなりますか？コストは大きな問題です。ですから、ここに助けを求めに来ました。少なくともいくつかのブロックシステムが必要ですか？
Input
いくつかのグループのデータを入力します。各グループのデータにはミサイルの総個数（正の整数）が含まれています。ミサイルはここから飛来する高さです。（レーダーが提供する高度データは30000以下の正の整数です。スペースで区切ります。）
Output
データ出力に対応してすべてのミサイルをブロックするには、少なくとも何セットのミサイル迎撃システムが必要ですか？
Sample Input
算法：贪心 || Dp 【本质一样】
http://acm.hdu.edu.cn/showproblem.php?pid=1257
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28195#problem/D
最小ブロックシステム
Time Limit：2000/1000 MS（Java/Others） メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：12863 Acceepted Submission（s）：5100
Problem Description
ある国は、敵国のミサイル攻撃を防ぐために、ミサイル迎撃システムを開発しました。しかし、このミサイル迎撃システムには、第一弾は任意の高度に到達することができますが、その後はどの砲弾も前発の高さを超えてはいけません。ある日、雷達は敵国のミサイル攻撃を捉えました。このシステムはまだ試用段階ですので、システムは一つしかありません。だから全てのミサイルは迎撃できないかもしれない。
どうすればいいですかもっとシステムを作ればいいです。簡単ですが、コストはどうなりますか？コストは大きな問題です。ですから、ここに助けを求めに来ました。少なくともいくつかのブロックシステムが必要ですか？
Input
いくつかのグループのデータを入力します。各グループのデータにはミサイルの総個数（正の整数）が含まれています。ミサイルはここから飛来する高さです。（レーダーが提供する高度データは30000以下の正の整数です。スペースで区切ります。）
Output
データ出力に対応してすべてのミサイルをブロックするには、少なくとも何セットのミサイル迎撃システムが必要ですか？
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
Source
浙江工业大学第四届大学生程序设计竞赛
Recommend
JGShining
算法：贪心 || Dp 【本质一样】
思路：
算是很简单的一道题目了，但是从这里 学会了所谓的 LIS 优化,所以想好好总结下了
开始是用贪心做的了，复杂度 O（n^2）最容易理解的一种写法了。
后来看了下这篇博客的分析：说是用“最长上升子序列的长度”http://www.cnblogs.com/dgsrz/articles/2384081.html
复杂度 O（n^2）高了点，还是比较好理解的了。
/*
( DP)
opt[i]=max(opt[j])+1, opt[i]) (0<=jnum[i]) { }
O(n^2)
*/
しかし、これはむしろ効率を欲しがるほうがいいです。その後LISの資料を探しました。
http://hi.baidu.com/freezhan/item/c681309ef81ebbd0291647ed
http://www.cnblogs.com/okboy/p/3224186.html
LISのO（nlogn）のアルゴリズムは実は欲张の本质と似ていることが分かりました。
サンプルのデータは：
389 207 155 300 299 170 158 65
欲張りな考えをする：
配列h[]でブロッキングシステムの現在のブロッキング高さを記録し、まず最大値INF=30000+10に初期化します。
新しい迎撃システムごとにすべてのミサイルを迎撃することができます。そしてミサイルに出会ったら、前に向かって探してみます。使用済みのシステムがあれば、迎撃できますか？さもないとシステムをリセットします。最後にいくつかのシステムを使ったらいいです。
最初のミサイル389第二のミサイル207第3弾155第四のミサイル300>h[1]、300第五のミサイル299>h[1]，299六番目のミサイル170>h[1]、1707番目のミサイル158 h[1]、158[h]h[2]=158
第八のミサイル65最後に二つのシステムを使って、ミサイルを全てブロックしました。
ミサイルの高さ：389 207 155 300 299 170 158
使用するブロッキングシステム：1 1 1 2 2 1
後輩がまとめているのを見ました。このような言葉がとてもいいです。
次にTeilwallの一言を借ります。
最長上昇サブシーケンスを求めます。
順序を指定した一連の列の中で、LISの長さを求めます。LISの長さは上昇しないサブシーケンスの数です。
DPのO(n^n)の考え方を説明します。
dp[i]はi番目のミサイルを迎撃するシステムの番号indexを記録しています。
先にすべてのミサイルを初期化します。最初のシステムによって阻止されます。dp[i]=1
dp[i]=max(dp[i]，dp[j]+1)【0<=j high[j]
i番目のミサイルに遭遇した時、前の方に迎撃されたミサイルを見るシステムはi番目のミサイル0をブロックすることができますか？
i番目のミサイルがj番目のミサイルよりも高くなると、上の欲張りな考え方でi番目のミサイルを迎撃するシステムはj番目のミサイルを迎撃するシステムよりも大きくなり、
最少の大きさは一つしかないです。もし（j＜k＜i）k番目のミサイルがi番目に低いものがないならば。
（はっきり言ったかどうか分かりませんが、とにかく分かりました。）
最後のdp[]に対応する値は上の欲張りな思想のh[]の下付きです。
ミサイル高さa[]：389 207 155 300 299 170 158
使用するブロッキングシステムdp[]：1 2 2 1
最後に出力する最大のdp[]は必要なシステムの個数です。
最後にDpのO（nlogn）の考えをまとめます。
実は本質はすべて同じです。この不思議なLISの最適化のように、変なネーミング方法は、私の大半を見てから分かります。
http://hi.baidu.com/freezhan/item/c681309ef81ebbd0291647ed
まず第1ラウンドはすべてのミサイルを遍歴しました。変えられないここではO（n）を消費します。
第二重循環を二点に変えただけです。二分複雑度O（logn）
まず私達が明確にしたいのは上のDp O(n^2)LIS思想の第二ラウンドは何ですか？
まず、h行列記憶ブロックシステムの高さを定義します。前の貪欲な分析によると、
私達はこの点を明確にすることができます。使用済みのシステムh[]であれば、それはきっと単調に増加します。
この時h[i]を使ったi番目のシステムは現在ミサイルの最高値を迎撃することができます。
ですから、第二ラウンドは前のh[index]==a[i]を探して、h[index]=a[i]を更新します。
永遠にh[]を維持するのは単調に増加したので、最後にh[]を出力するのは長さを使って、或いは上の欲張りのように繰り返し数えていくつのh[]を使ってもいいです。
じゃ、また私達の肝心な問題に戻ります。どうやって第二ラウンドの順序検索O（n）をO（logn）に最適化しますか？
注意：h[]は常に単調に増分されますので、直接に二点検索を書いてください。基本的にこの問題については0秒を超えてもいいです。
最終的には、これもインターネット上にアップロードされたLISの最良の解法であることが分かりました。
もし怠けたいなら、二点も書かなくてもいいです。直接にalgorithmのヘッダファイルを追加して、lowerを呼び出します。boundがいいですね。【kuangbin大神教のOrz】int index = lower_bound(h,h+len+1,a[i])-h; // h[index] h >= a[i]
lowerについてboundとuper_bound:
lower.boundが返したのは>=検索した数の最初の下付きです。
uper_boundは'検索した数の最初の下付き文字を返します。
すべては配列の中で左と右の間に検索されます。
境界を越える場合：検索された数>配列中のすべての数が、配列の末尾の下付きに戻り、このとき配列が境界を越えます。
次にコードを順次貼ります。読めない出力中間変数がいいです。
コード:
欲張り：
D
Acceepted
236 KB
15 ms
C++
746 B#include
#include
#include
using namespace std;
const int maxn = 1000+10;
const int INF = 30000+10; // 30000
int a[maxn]; //
int h[maxn]; // h[i] i
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
h[i] = INF; //
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j <= i; j++) // , , , i
{
if(h[j] >= a[i]) //
{
h[j] = a[i]; // j i ,
break; // i ,
}
}
}
int tot = 0;
for(int i = 0; i < n; i++) //
if(h[i] != INF) // i
tot++;
printf("%d
", tot);
}
return 0;
}
DPのO(n^n)
D
Acceepted
236 KB
15 ms
C++
792 B/*****************************************************
dp[i] = max(dp[i], dp[j]+1) 【0<=j a[j]】
i > j ,
i , j
******************************************************/
#include
#include
using namespace std;
const int maxn = 1000+10;
const int INF = 30000+10;
int a[maxn]; //
int dp[maxn]; //d[i] i dp[i]
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
dp[i] = 1;
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < i; j++)
if(a[i] > a[j])
dp[i] = max(dp[i], dp[j]+1);
}
int ans = 0;
for(int i = 0; i < n; i++)
ans = max(ans, dp[i]);
printf("%d
", ans);
}
return 0;
}
DpのO(nlogn)二分検索：
D
Acceepted
236 KB
0 ms
C++
959 B#include
#include
using namespace std;
const int maxn = 1000+10;
int a[maxn]; //
int h[maxn]; // h[i] i
int find(int h[], int len, int ha) // index , h[] , h[index] >= ha
{
int left = 0;
int right = len;
while(left <= right)
{
int mid = (left+right) / 2;
if(ha > h[mid]) left = mid+1;
else if(ha < h[mid]) right = mid-1;
else return mid;
}
return left;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
h[0] = -1;
h[1] = a[0];
int len = 1;
for(int i = 1; i < n; i++)
{
int index = find(h,len, a[i]);
h[index] = a[i];
//printf("test : h[%d] = %d
", index, h[index]);
if(index > len)
len = index;
}
printf("%d
", len);
}
return 0;
}
Dp O(nlogn)の直接呼び出しlower検索
D
Acceepted
236 KB
0 ms
C++
814 B
2013-08-05 11:34:41#include
#include
#include
using namespace std;
const int maxn = 1000+10;
int a[maxn];
int h[maxn];
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
h[0] = -1;
h[1] = a[0];
int len = 1;
for(int i = 1; i < n; i++)
{
int index = lower_bound(h,h+len+1,a[i])-h;
h[index] = a[i];
//printf("test: h[%d] = %d
", index, h[index]);
if(index > len)
len = index;
}
printf("%d
", len);
}
return 0;
}
算是很简单的一道题目了，但是从这里 学会了所谓的 LIS 优化,所以想好好总结下了
开始是用贪心做的了，复杂度 O（n^2）最容易理解的一种写法了。
后来看了下这篇博客的分析：说是用“最长上升子序列的长度”http://www.cnblogs.com/dgsrz/articles/2384081.html
复杂度 O（n^2）高了点，还是比较好理解的了。
/*
( DP)
opt[i]=max(opt[j])+1, opt[i]) (0<=jnum[i]) { }
O(n^2)
*/http://hi.baidu.com/freezhan/item/c681309ef81ebbd0291647ed
http://www.cnblogs.com/okboy/p/3224186.html
LISのO（nlogn）のアルゴリズムは実は欲张の本质と似ていることが分かりました。
サンプルのデータは：
389 207 155 300 299 170 158 65
欲張りな考えをする：
配列h[]でブロッキングシステムの現在のブロッキング高さを記録し、まず最大値INF=30000+10に初期化します。
新しい迎撃システムごとにすべてのミサイルを迎撃することができます。そしてミサイルに出会ったら、前に向かって探してみます。使用済みのシステムがあれば、迎撃できますか？さもないとシステムをリセットします。最後にいくつかのシステムを使ったらいいです。
最初のミサイル389
第八のミサイル65
ミサイルの高さ：389 207 155 300 299 170 158
使用するブロッキングシステム：1 1 1 2 2 1
後輩がまとめているのを見ました。このような言葉がとてもいいです。
次にTeilwallの一言を借ります。
最長上昇サブシーケンスを求めます。
順序を指定した一連の列の中で、LISの長さを求めます。LISの長さは上昇しないサブシーケンスの数です。
DPのO(n^n)の考え方を説明します。
dp[i]はi番目のミサイルを迎撃するシステムの番号indexを記録しています。
先にすべてのミサイルを初期化します。最初のシステムによって阻止されます。dp[i]=1
dp[i]=max(dp[i]，dp[j]+1)【0<=j high[j]
i番目のミサイルに遭遇した時、前の方に迎撃されたミサイルを見るシステムはi番目のミサイル0をブロックすることができますか？
i番目のミサイルがj番目のミサイルよりも高くなると、上の欲張りな考え方でi番目のミサイルを迎撃するシステムはj番目のミサイルを迎撃するシステムよりも大きくなり、
最少の大きさは一つしかないです。もし（j＜k＜i）k番目のミサイルがi番目に低いものがないならば。
（はっきり言ったかどうか分かりませんが、とにかく分かりました。）
最後のdp[]に対応する値は上の欲張りな思想のh[]の下付きです。
ミサイル高さa[]：389 207 155 300 299 170 158
使用するブロッキングシステムdp[]：1 2 2 1
最後に出力する最大のdp[]は必要なシステムの個数です。
最後にDpのO（nlogn）の考えをまとめます。
実は本質はすべて同じです。この不思議なLISの最適化のように、変なネーミング方法は、私の大半を見てから分かります。
http://hi.baidu.com/freezhan/item/c681309ef81ebbd0291647ed
まず第1ラウンドはすべてのミサイルを遍歴しました。変えられないここではO（n）を消費します。
第二重循環を二点に変えただけです。二分複雑度O（logn）
まず私達が明確にしたいのは上のDp O(n^2)LIS思想の第二ラウンドは何ですか？
まず、h行列記憶ブロックシステムの高さを定義します。前の貪欲な分析によると、
私達はこの点を明確にすることができます。使用済みのシステムh[]であれば、それはきっと単調に増加します。
この時h[i]を使ったi番目のシステムは現在ミサイルの最高値を迎撃することができます。
ですから、第二ラウンドは前のh[index]==a[i]を探して、h[index]=a[i]を更新します。
永遠にh[]を維持するのは単調に増加したので、最後にh[]を出力するのは長さを使って、或いは上の欲張りのように繰り返し数えていくつのh[]を使ってもいいです。
じゃ、また私達の肝心な問題に戻ります。どうやって第二ラウンドの順序検索O（n）をO（logn）に最適化しますか？
注意：h[]は常に単調に増分されますので、直接に二点検索を書いてください。基本的にこの問題については0秒を超えてもいいです。
最終的には、これもインターネット上にアップロードされたLISの最良の解法であることが分かりました。
もし怠けたいなら、二点も書かなくてもいいです。直接にalgorithmのヘッダファイルを追加して、lowerを呼び出します。boundがいいですね。【kuangbin大神教のOrz】
int index = lower_bound(h,h+len+1,a[i])-h; // h[index] h >= a[i] lower.boundが返したのは>=検索した数の最初の下付きです。
uper_boundは'検索した数の最初の下付き文字を返します。
すべては配列の中で左と右の間に検索されます。
境界を越える場合：検索された数>配列中のすべての数が、配列の末尾の下付きに戻り、このとき配列が境界を越えます。
次にコードを順次貼ります。読めない出力中間変数がいいです。
コード:
欲張り：
D
Acceepted
236 KB
15 ms
C++
746 B
#include
#include
#include
using namespace std;
const int maxn = 1000+10;
const int INF = 30000+10; // 30000
int a[maxn]; //
int h[maxn]; // h[i] i
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
h[i] = INF; //
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j <= i; j++) // , , , i
{
if(h[j] >= a[i]) //
{
h[j] = a[i]; // j i ,
break; // i ,
}
}
}
int tot = 0;
for(int i = 0; i < n; i++) //
if(h[i] != INF) // i
tot++;
printf("%d
", tot);
}
return 0;
}
D
Acceepted
236 KB
15 ms
C++
792 B
/*****************************************************
dp[i] = max(dp[i], dp[j]+1) 【0<=j a[j]】
i > j ,
i , j
******************************************************/
#include
#include
using namespace std;
const int maxn = 1000+10;
const int INF = 30000+10;
int a[maxn]; //
int dp[maxn]; //d[i] i dp[i]
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
dp[i] = 1;
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < i; j++)
if(a[i] > a[j])
dp[i] = max(dp[i], dp[j]+1);
}
int ans = 0;
for(int i = 0; i < n; i++)
ans = max(ans, dp[i]);
printf("%d
", ans);
}
return 0;
}
D
Acceepted
236 KB
0 ms
C++
959 B
#include
#include
using namespace std;
const int maxn = 1000+10;
int a[maxn]; //
int h[maxn]; // h[i] i
int find(int h[], int len, int ha) // index , h[] , h[index] >= ha
{
int left = 0;
int right = len;
while(left <= right)
{
int mid = (left+right) / 2;
if(ha > h[mid]) left = mid+1;
else if(ha < h[mid]) right = mid-1;
else return mid;
}
return left;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
h[0] = -1;
h[1] = a[0];
int len = 1;
for(int i = 1; i < n; i++)
{
int index = find(h,len, a[i]);
h[index] = a[i];
//printf("test : h[%d] = %d
", index, h[index]);
if(index > len)
len = index;
}
printf("%d
", len);
}
return 0;
}
D
Acceepted
236 KB
0 ms
C++
814 B
2013-08-05 11:34:41
#include
#include
#include
using namespace std;
const int maxn = 1000+10;
int a[maxn];
int h[maxn];
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
h[0] = -1;
h[1] = a[0];
int len = 1;
for(int i = 1; i < n; i++)
{
int index = lower_bound(h,h+len+1,a[i])-h;
h[index] = a[i];
//printf("test: h[%d] = %d
", index, h[index]);
if(index > len)
len = index;
}
printf("%d
", len);
}
return 0;
}