hdu1160

題意：給出很多老鼠的數(shù)據(jù)，分別是它們的體重和跑速，為了證明老鼠越重跑得越慢，要找一組數(shù)據(jù)，由若干個老鼠組成，保證老鼠的體重依次增加而跑速依次減小，問這組數(shù)據(jù)最多能有多少老鼠，并按體重從小到大輸出這些老鼠的順序。

并不是難題，我覺得有點(diǎn)類似窮國富國或者是堆磚塊，我的做法就是首先將這些老鼠按體重從大到小排序（為什么從大到小呢，因?yàn)槲沂怯媒Y(jié)構(gòu)體模擬指針記錄了上一只老鼠的序號，所以最終會倒序輸出，排序的時候就按倒序排序了）

昂，介紹下我的結(jié)構(gòu)體，是記錄了 w（weight），s（speed），n（number），l（last），體重和速度肯定是要記錄的用于比較，n 是由于我要進(jìn)行排序，數(shù)組下標(biāo)會被打亂，所以用 n 單獨(dú)記錄這只老鼠原本的位置，l 則是記錄這只老鼠上一只老鼠的數(shù)組下標(biāo)，如果前面沒有老鼠，那就是指向第 0 只老鼠（重量是極大，速度是 0，n 、 l 都初始化為0）.

當(dāng)對體重排完序之后，就從前往后開始 dp ，對第 i 只老鼠，遍歷從 0 到 i - 1 的老鼠 j ，如果 j 比 i 重而且速度慢，那就 dp[ i ] = max ( dp [ i ] , dp [ j ] + 1 )，并且判斷 dp [ i ] 是不是最大值，如果是就記錄下 i 便于最后輸出數(shù)據(jù)量最大的一組老鼠。

然后就這么結(jié)束了。

?

恩，接下來是吐槽時間，看見我代碼里面一堆堆綠翔色的 debug 代碼了嗎```是的，一開始我讀入都不對，我計數(shù)的 c 是在讀取數(shù)據(jù)的時候 ++c 的，但是每次讀兩個數(shù)據(jù)，我就很自以為是地一個用了 ++c 一個直接 c，以為會在第一個加了，第二個就是沿用加過的，于是```各種坑，++這種東西還是要足夠水平才能用啊，我這種渣渣還是老老實(shí)實(shí)后面加 c++ 吧```；

這并不是全部，然后我在糾結(jié)樣例那個順序究竟是怎么得到的呢！！！為什么我每次都和它有一兩個不一樣，我試了要不要排速度？ dp 值相等的時候要不要取？各種各種，正當(dāng)我即將絕望想要求助學(xué)長的時候```我突然看到說只要求一種可行解就可以了！！！英語啊我的英語啊誰來拯救我的英語啊！！！

恩并不止是這樣，當(dāng)我明白是其中一種正確解就可以的時候我果斷提交！WA！！！WTF！！！我換了種姿勢又WA了一發(fā)，我覺得是時候找學(xué)長們談?wù)撘幌氯松?#96;``然后我突然又發(fā)現(xiàn)```由于讀入的時候沒有說讀入多少個只是讀到文件結(jié)束，所以我自己加了個讀 9 個數(shù)據(jù)就跳出讀取循環(huán)為了測試給的樣例，但是我并記不住把它刪掉！```果然把它注釋掉就 AC 了，我的心好累，連 hdu 都要欺負(fù)我這種智商不過關(guān)的渣渣啊```

?

1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 #define max(a,b) a>b?a:b 6 #define inf 0x3f3f3f3f 7 int dp[1050]; 8 9 struct Mouse{ 10 int w,s,n,l; 11 }m[1050]; 12 13 int cmp(Mouse m1,Mouse m2){ 14 if(m1.w==m2.w)return m1.s<m2.s; 15 return m1.w>m2.w; 16 } 17 18 int main(){ 19 int c=1,i,j; 20 while(scanf("%d%d",&m[c].w,&m[c].s)!=EOF){ 21 m[c].n=c; 22 m[c].l=0; 23 // if(c==9)break; 24 c++; 25 } 26 /* 27 printf("\n"); 28 for(i=1;i<=c;i++)printf("%d %d\n",m[i].w,m[i].s); 29 printf("\n"); 30 */ 31 sort(m+1,m+c+1,cmp); 32 m[0].w=inf; 33 m[0].s=0; 34 m[0].l=0; 35 m[0].n=0; 36 int ans=0; 37 /* printf("\n"); 38 for(i=0;i<=c;i++){ 39 printf("%d %d\n",m[i].w,m[i].s); 40 } 41 printf("\n"); 42 */ for(i=1;i<=c;i++){ 43 dp[i]=0; 44 for(j=0;j<i;j++){ 45 if(m[j].w>m[i].w&&m[j].s<m[i].s){ 46 if(dp[j]+1>=dp[i]){ 47 dp[i]=dp[j]+1; 48 m[i].l=j; 49 if(dp[i]>dp[ans])ans=i; 50 } 51 } 52 } 53 } 54 printf("%d\n",dp[ans]); 55 while(m[ans].l!=0){ 56 // printf("%d %d ",m[ans].w,m[ans].s); 57 printf("%d\n",m[ans].n); 58 ans=m[ans].l; 59 } 60 // printf("%d %d ",m[ans].w,m[ans].s); 61 printf("%d\n",m[ans].n); 62 return 0; 63 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/cenariusxz/p/4290837.html

總結(jié)

以上是生活随笔為你收集整理的hdu1160 dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。