hdu 1421:寝室を運ぶ(ダイナミックプランニングDP+ソート)
10103 ワード
寝室を運ぶ.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 14107 Accepted Submission(s): 4751
Problem Description
2006年7月9日、その日xhdは仕方なく27号棟から3号棟に引っ越しなければならなかった.10号は閉鎖されるからだ.寝室のn件の品物を見て、xhdはぼんやりし始めた.nは2000未満の整数で、本当に多すぎるので、xhdは勝手に2*k件を運んで行けばいいと決めた.しかし、やはり疲れてしまう.2*kも小さくないのでn以下の整数である.幸いなことにxhdは長年の持ち物の経験から左右の手のものの重量差の二乗に比例することが分かった.例えばxhdは左手に重量3のものを持ち,右手に重量6のものを持ち,彼の今回の疲労度は(6-3)^2=9.今かわいそうなxhdはこの2*k件の荷物を運んだ後の最良の状態がどのようなものか(つまり最低の疲労度)を知りたいので、教えてください.
Input
各入力データは2行あり、1行目は2個の数n,k(2<=2*k<=n<2000)である、2行目はn個の整数がそれぞれn個の物品の重量(重量は2^15未満の正の整数)を表す.
Output
各入力データのセットに対応する出力データは、彼の最低疲労度を示す1行のみである.
Sample Input
2 1 1 3
Sample Output
4
Author
xhd
Source
ACM夏休み合宿チーム練習試合(二)
Recommend
lcy | We have carefully selected several similar problems for you:
1176
1087
1058
1069
1203
古典的な動的計画問題.
これはダイナミックな計画の水問題ですが、ゲージがまだはっきりしない状態の私はとても骨が折れると思います.他の人の解題報告書を見て、N多脳細胞がつまずいて状態転移方程式を書いた.
dp[i][j]は、前のiつの物品からj対の搬送をとる最小疲労値を表す.
私の考えはあまりはっきりしていないので、他の人のリンクを貼って、興味のある人は高人が書いたのを見ることができます.
HDU 1421寝室を運ぶ HDu 1421 nで選択したk個の隣接しない数の最小値 hdu 1421寝室を運ぶ
私が言いたいのは2点に注意して、最初は自分で書いたバブルソートを使って、それからタイムアウトを提出して、ネット上のコードを見て大部分が直接ライブラリ関数(qsort、sort関数のようです)を呼び出して、私はsort関数を変えてからタイムアウトしないで、良いソートアルゴリズムが問題をする中でやはりとても役に立ちます!その後WAの現象が発生し、デバッグはこれがdp配列の初期化に起因しないことを発見した.サイズを比較するには小さい値をとる必要があるため、極大値(例えば9999999999)に初期化すべきであり、dp[i][0]という一連の数は0に初期化する必要がある.
コードは次のとおりです.
Run ID
Submit Time
Judge Status
Pro.ID
Exe.Time
Exe.Memory
Code Len.
Language
Author
10011975
2014-01-22 20:13:55
Accepted
1421
750MS
8228K
750 B
G++
freecode
Freecode : www.cnblogs.com/yym2013
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 14107 Accepted Submission(s): 4751
Problem Description
2006年7月9日、その日xhdは仕方なく27号棟から3号棟に引っ越しなければならなかった.10号は閉鎖されるからだ.寝室のn件の品物を見て、xhdはぼんやりし始めた.nは2000未満の整数で、本当に多すぎるので、xhdは勝手に2*k件を運んで行けばいいと決めた.しかし、やはり疲れてしまう.2*kも小さくないのでn以下の整数である.幸いなことにxhdは長年の持ち物の経験から左右の手のものの重量差の二乗に比例することが分かった.例えばxhdは左手に重量3のものを持ち,右手に重量6のものを持ち,彼の今回の疲労度は(6-3)^2=9.今かわいそうなxhdはこの2*k件の荷物を運んだ後の最良の状態がどのようなものか(つまり最低の疲労度)を知りたいので、教えてください.
Input
各入力データは2行あり、1行目は2個の数n,k(2<=2*k<=n<2000)である、2行目はn個の整数がそれぞれn個の物品の重量(重量は2^15未満の正の整数)を表す.
Output
各入力データのセットに対応する出力データは、彼の最低疲労度を示す1行のみである.
Sample Input
2 1 1 3
Sample Output
4
Author
xhd
Source
ACM夏休み合宿チーム練習試合(二)
Recommend
lcy | We have carefully selected several similar problems for you:
1176
1087
1058
1069
1203
古典的な動的計画問題.
これはダイナミックな計画の水問題ですが、ゲージがまだはっきりしない状態の私はとても骨が折れると思います.他の人の解題報告書を見て、N多脳細胞がつまずいて状態転移方程式を書いた.
dp[i][j] = Min ( dp[i-2][j-1] + (a[i]-a[i-1]) * (a[i]-a[i-1]) , dp[i-1][j] ) ;dp[i][j]は、前のiつの物品からj対の搬送をとる最小疲労値を表す.
私の考えはあまりはっきりしていないので、他の人のリンクを貼って、興味のある人は高人が書いたのを見ることができます.
HDU 1421寝室を運ぶ HDu 1421 nで選択したk個の隣接しない数の最小値 hdu 1421寝室を運ぶ
私が言いたいのは2点に注意して、最初は自分で書いたバブルソートを使って、それからタイムアウトを提出して、ネット上のコードを見て大部分が直接ライブラリ関数(qsort、sort関数のようです)を呼び出して、私はsort関数を変えてからタイムアウトしないで、良いソートアルゴリズムが問題をする中でやはりとても役に立ちます!その後WAの現象が発生し、デバッグはこれがdp配列の初期化に起因しないことを発見した.サイズを比較するには小さい値をとる必要があるため、極大値(例えば9999999999)に初期化すべきであり、dp[i][0]という一連の数は0に初期化する必要がある.
コードは次のとおりです.
1 #include <iostream>
2 #include <algorithm>
3 #include <string.h>
4 using namespace std; 5 int dp[2001][1001]; 6 int Min(int a,int b) 7 { 8 //if(a==0) 9 // return b; 10 //if(b==0) 11 // return a;
12 return a<b?a:b; 13 } 14 int main() 15 { 16 int n,k; 17 while(cin>>n>>k){ 18 int a[2001]; 19 for(int i=1;i<=n;i++) 20 cin>>a[i]; 21 //
22 /* 23 for(int i=1;i<=n-1;i++) 24 for(int j=1;j<=n-i;j++) 25 if(a[j]>a[j+1]){ 26 int t; 27 t=a[j];a[j]=a[j+1];a[j+1]=t; 28 } 29 */
30 sort(a+1,a+1+n); 31
32 //
33 memset(dp,9999999,sizeof(dp)); 34 for(int i=0;i<=n;i++) 35 dp[i][0] = 0; 36
37 // dp
38 for(int i=2;i<=n;i++) 39 for(int j=1;j<=i/2;j++){ 40 dp[i][j] = Min(dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]),dp[i-1][j]); 41 } 42 cout<<dp[n][k]<<endl; 43 } 44
45 return 0; 46 }Run ID
Submit Time
Judge Status
Pro.ID
Exe.Time
Exe.Memory
Code Len.
Language
Author
10011975
2014-01-22 20:13:55
Accepted
1421
750MS
8228K
750 B
G++
freecode
Freecode : www.cnblogs.com/yym2013