藍(lán)橋杯vip試題以及答案解析

1、 /首先聲明這并不是本人原創(chuàng)，只不不過本人想總結(jié)出來方便大家，全為C+代碼。1.結(jié)點(diǎn)選擇問題描述有一棵 n 個(gè)節(jié)點(diǎn)的樹，樹上每個(gè)節(jié)點(diǎn)都有一個(gè)正整數(shù)權(quán)值。如果一個(gè)點(diǎn)被選擇了，那么在樹上和它相鄰的點(diǎn)都不能被選擇。求選出的點(diǎn)的權(quán)值和最大是多少？解題思路：這題模型是樹形動態(tài)規(guī)劃入門題目，dpi0表示該節(jié)點(diǎn)不被選擇，dpi1表示該結(jié)點(diǎn)被選擇。轉(zhuǎn)移方程為:dpu1+=dpv0;/選擇了u結(jié)點(diǎn)，則與它鄰接的結(jié)點(diǎn)不選；dpu0+=max(dpv0，dpv1);不選擇u結(jié)點(diǎn)，則與它鄰接的結(jié)點(diǎn)選擇結(jié)果最大的；應(yīng)該特別注意：該題結(jié)點(diǎn)數(shù)量較大，應(yīng)該選用鄰接表存儲邊的關(guān)系1. #include<cstd

2、io>  2. #include<cstring>  3. #define max(a,b) (a)>(b)?(a):(b)  4. #define maxn 100010  5. bool vismaxn;  6. int dpmaxn2;  7. int fathermaxn;  8. int headmaxn;  9. int&

3、#160;n;  10. int cnt;  11. struct Edge  12.   13.     int to,next;  14. edge2*maxn;  15. void add(int u,int v)  16.   17.     edgecnt.to=v;  

4、;18.     edgecnt.next=headu;  19.     headu=cnt+;  20.   21. void treedp(int u)  22.   23.     visu=1;  24.     for(int i=headu;i!=-1;i=edgei.nex

5、t)  25.       26.         int v=edgei.to;  27.         if(!visv)  28.           29.    

6、60;        treedp(v);  30.             dpu1+=dpv0;  31.             dpu0+=max(dpv1,dpv0);  32.   

7、60;       33.       34.   35. void init()  36.   37.     cnt=0;  38.     memset(dp,0,sizeof(dp);  39.     memset(father,

8、0,sizeof(father);  40.     memset(vis,0,sizeof(vis);  41.     memset(head,-1,sizeof(head);  42.   43. int main()  44.   45.     init();  46.     

9、scanf("%d",&n);  47.     for(int i=1;i<=n;i+)  48.     scanf("%d",&dpi1);  49.     int root=0;  50.     int begin=1;  51. &#

10、160;   for(int i=0;i<n-1;i+)  52.       53.         int a,b;  54.         scanf("%d%d",&a,&b);  55.   &#

11、160;     add(a,b);  56.         add(b,a);  57.         fatherb=a;  58.         if(root=b|begin)  59.   &#

12、160;       60.             root=a;  61.           62.       63.       64.   

13、;  while(fatherroot)  65.     root=fatherroot;  66.     treedp(root);  67.     int ans;  68.     ans=max(dproot0,dproot1);  69.     pri

14、ntf("%dn",ans);  70.   2.K好數(shù)  問題描述如果一個(gè)自然數(shù)N的K進(jìn)制表示中任意的相鄰的兩位都不是相鄰的數(shù)字，那么我們就說這個(gè)數(shù)是K好數(shù)。求L位K進(jìn)制數(shù)中K好數(shù)的數(shù)目。例如K = 4，L = 2的時(shí)候，所有K好數(shù)為11、13、20、22、30、31、33 共7個(gè)。由于這個(gè)數(shù)目很大，請你輸出它對1000000007取模后的值。解題思路：dpij表示第i位為j的時(shí)候的個(gè)I好數(shù)個(gè)數(shù)；因此有轉(zhuǎn)移方程：dpij=dpi-1m+dpij;m為上一位的值，滿足的條件應(yīng)為m-j的絕對值不為1.即不相鄰；應(yīng)當(dāng)注意的是：最

15、后在求和的時(shí)候不能簡單的統(tǒng)計(jì)dplm 0<=m<k;因?yàn)槭孜蝗绻?的話，其實(shí)不足L位了，所以0<m<k,也許有人會疑問這是不統(tǒng)計(jì)L位的0，不是第一位呀。其實(shí)仔細(xì)想想，是等效的。1. #include<cstdio>  2. #include<cstring>  3. #define mod 1000000007  4. #define abs(a,b) (a)>(b)?(a-b):(b-a)  5. int d

16、p110110;  6. int main()  7.   8.     int k,l;  9.     memset(dp,0,sizeof(dp);  10.     scanf("%d%d",&k,&l);  11.     for(int i=

17、0;i<k;i+)  12.     dp1i=1;  13.     for(int i=2;i<=l;i+)  14.       15.         for(int j=0;j<k;j+)  16.     &#

18、160;     17.             for(int m=0;m<k;m+)  18.               19.           

19、;      if(abs(m,j)!=1)  20.                 dpij=(dpij%mod+dpi-1m%mod)%mod;  21.               22. &

20、#160;         23.       24.     int ans=0;  25.     for(int i=1;i<k;i+)  26.     ans=(ans%mod+dpli%mod)%mod;  27.  &#

21、160;  printf("%dn",ans);  28.   3. 操作格子問題描述有n個(gè)格子，從左到右放成一排，編號為1-n。共有m次操作，有3種操作類型：1.修改一個(gè)格子的權(quán)值，2.求連續(xù)一段格子權(quán)值和，3.求連續(xù)一段格子的最大值。對于每個(gè)2、3操作輸出你所求出的結(jié)果。解題思路：這是線段樹的入門題目。直接建立線段樹，求解就OK了1. #include<cstdio>  2. #define max(a,b) (a)>(b)?(a):(b) &

22、#160;3. #define min(a,b) (a)<(b)?(a):(b)  4. #define N 100010  5. #define L(a) (a)<<1  6. #define R(a) (a)<<1|1  7. struct node  8.   9.    int l,r,maxn,minn,su

23、m;  10. line3*N;  11. int numN;  12. int first,second;  13. void create(int k,int x,int y)  14.   15.    linek.l=x;linek.r=y;  16.    if(x=y)  17.   &

24、#160;  18.       linek.sum=numx;  19.       linek.maxn=linek.minn=numx;  20.       return;  21.      22.    int mid=(x+y)>

25、>1;  23.    create(L(k),x,mid);  24.    create(R(k),mid+1,y);  25.    linek.maxn=max(lineL(k).maxn,lineR(k).maxn);  26.    /linek.minn=mymin(lineL(k).minn,lineR(k).minn);  27.   

26、; linek.sum=lineL(k).sum+lineR(k).sum;  28.   29. void updata(int k,int a,int b)  30.   31.     if(linek.l=linek.r)  32.       33.        &#

27、160;linek.maxn=b;  34.         linek.sum=b;  35.         return   36.       37.     int mid=(linek.l+linek.r)>>1;  

28、;38.     if(a<=mid)  39.     updata(L(k),a,b);  40.     else  41.     updata(R(k),a,b);  42.     linek.sum=lineL(k).sum+lineR(k).sum;  43.  &#

29、160;  linek.maxn=max(lineL(k).maxn,lineR(k).maxn);  44.   45. void quary(int k,int x,int y)  46.   47.    if(linek.l=x&&linek.r=y)  48.      49.     

30、60; second+=linek.sum;  50.       first=max(first,linek.maxn);  51.       return;  52.      53.    int mid=(linek.l+linek.r)>>1;  54.  

31、0; if(y<=mid)  55.        quary(L(k),x,y);  56.    else if(x>mid)  57.        quary(R(k),x,y);  58.    else  59.    

32、60; 60.       quary(L(k),x,mid);  61.       quary(R(k),mid+1,y);   62.      63.   64. int main()  65.   66.     int n,m; 

33、; 67.     scanf("%d%d",&n,&m);  68.     for(int i=1;i<=n;i+)  69.     scanf("%d",&numi);  70.     create(1,1,n);  71.    

34、; for(int i=1;i<=m;i+)  72.       73.         int a,b,c;  74.         scanf("%d%d%d",&a,&b,&c);  75.    &

35、#160;    if(a=1)  76.           77.             updata(1,b,c);  78.           79.    

36、     else if(a=2)  80.           81.             first=-10000;  82.             

37、second=0;  83.             quary(1,b,c);  84.             printf("%dn",second);  85.          &

38、#160;86.         else  87.           88.             first=-10000;  89.          

39、0;  second=0;  90.             quary(1,b,c);  91.             printf("%dn",first);  92.        

40、   93.           94.       95.   4. 2n皇后問題描述給定一個(gè)n*n的棋盤，棋盤中有一些位置不能放皇后?，F(xiàn)在要向棋盤中放入n個(gè)黑皇后和n個(gè)白皇后，使任意的兩個(gè)黑皇后都不在同一行、同一列或同一條對角線上，任意的兩個(gè)白皇后都不在同一行、同一列或同一條對角線上。問總共有多少種放法？n小于等于8。   解題思路：   深搜

41、黑皇后的可能分布，達(dá)到n時(shí)候深搜白皇后。1. #include<cstdio>  2. #include<iostream>  3. #include<cstring>  4. #include<algorithm>  5. using namespace std;  6. int ans;  7. bool row10,col10;  8. int maze

42、1010;  9. int n;  10. bool z20,f20;  11. int c20;  12. void dd(int cur)/這一段對白皇后的搜索為白書中對八皇后問題求解的代碼  13.   14.     int i,j;  15.     if(cur=n)  16. 

43、0;   ans+;  17.     else  18.     for(i=0;i<n;i+)  19.       20.         int ok=1;  21.       

44、60; if(mazecuri=0)  22.         continue;  23.         ccur=i;  24.         for(int j=0;j<cur;j+)  25.     

45、      26.             if(ccur=cj|cur-ccur=j-cj|cur+ccur=j+cj)  27.               28.        

46、60;        ok=0;  29.                 break;  30.               31.    

47、0;      32.         if(ok)  33.         dd(cur+1);  34.       35.   36. void dfs(int count)  37.   3

48、8.     if(count=n)  39.       40.         dd(0);  41.         return   42.       43.    &#

49、160;for(int j=0;j<n;j+)  44.       45.         if(!rowcount&&!colj&&mazecountj=1&&!zcount+j&&!fn-1-j+count)  46.          

50、60;47.             zcount+j=true;  48.             fn-1-j+count=true;  49.             rowcount=true

51、;  50.             colj=true;  51.             mazecountj=0;  52.             dfs(count+1)

52、;  53.             zcount+j=false;  54.             fn-1-j+count=false;  55.             r

53、owcount=false;  56.             colj=false;  57.             mazecountj=1;  58.           59.  

54、     60.     return   61.   62. int main()  63.   64.     cin>>n;     65.     for(int i=0;i<n;i+)  66.   &

55、#160; for(int j=0;j<n;j+)  67.     cin>>mazeij;  68.     memset(row,0,sizeof(row);  69.     memset(col,0,sizeof(col);  70.     memset(z,0,sizeof(z);  7

56、1.     memset(f,0,sizeof(f);  72.     memset(c,-1,sizeof(c);  73.     ans=0;  74.     dfs(0);  75.     cout<<ans<<endl;  76.   &

57、#160;   77.   5.  回形取數(shù) 問題描述回形取數(shù)就是沿矩陣的邊取數(shù)，若當(dāng)前方向上無數(shù)可取或已經(jīng)取過，則左轉(zhuǎn)90度。一開始位于矩陣左上角，方向向下。解題思路：    直接按下，右，上，左的方向進(jìn)行深搜即可。同樣也可以用while循環(huán)實(shí)現(xiàn)，速度要比深搜快。1. #include<cstdio>  2. #include<iostream>  3. #include<cstring>  4. #incl

58、ude<algorithm>  5. #define fr(i,n) for(int i=0;i<n;i+)  6. #define set(a,b) memset(a,b,sizeof(a)  7. using namespace std;  8. int m,n;  9. int maze210210;  10. bool vis210210; 

59、 11. int tt;  12. int ans50000;  13. bool in(int x,int y)  14.   15.     if(x>=0&&x<m&&y>=0&&y<n)  16.     return true;  17. 

60、0;   return false;  18.   19. void dfs(int x,int y,int dir)  20.   21.     visxy=1;  22.     anstt+=mazexy;  23.     if(dir=0)  24

61、.       25.         if(in(x+1,y)&&!visx+1y)  26.         dfs(x+1,y,0);  27.         else if(in(x,y+1)&&!visxy

62、+1)  28.         dfs(x,y+1,1);  29.       30.     else if(dir=1)  31.       32.         if(in(x,y+1)&

63、&!visxy+1)  33.         dfs(x,y+1,1);  34.         else if(in(x-1,y)&&!visx-1y)  35.         dfs(x-1,y,2);  36.   

64、;    37.     else if(dir=2)  38.       39.         if(in(x-1,y)&&!visx-1y)  40.         dfs(x-1,y,2);  41.

65、        else if(in(x,y-1)&&!visxy-1)  42.         dfs(x,y-1,3);  43.       44.     else if(dir=3)  45.    &

66、#160;  46.         if(in(x,y-1)&&!visxy-1)  47.         dfs(x,y-1,3);  48.         else if(in(x+1,y)&&!visx+1y)  49. &#

67、160;       dfs(x+1,y,0);  50.       51.   52. int main()  53.   54.       55.     cin>>m>>n;  56.    &#

68、160;tt=0;  57.     set(vis,0);  58.     set(ans,0);  59.       60.     fr(i,m)  61.     fr(j,n)  62.     cin>>maze

69、ij;  63.     dfs(0,0,0);  64.     int t=0;  65.     fr(i,m)  66.     fr(j,n)  67.     if(i=m-1&&j=n-1)  68.    &

70、#160;cout<<anst+<<endl;  69.     else  70.     cout<<anst+<<" "  71.   6.  2的次冪表示問題描述任何一個(gè)正整數(shù)都可以用2進(jìn)制表示，例如：137的2進(jìn)制表示為10001001。將這種2進(jìn)制表示寫成2的次冪的和的形式，令次冪高的排在前面，可得到如下表達(dá)式：137=27+23+20現(xiàn)

71、在約定冪次用括號來表示，即ab表示為a（b）此時(shí)，137可表示為：2（7）+2（3）+2（0）進(jìn)一步：7=22+2+20 （21用2表示）3=2+20 所以最后137可表示為：2（2（2）+2+2（0）+2（2+2（0）+2（0）又如：1315=210+28+25+2+1所以1315最后可表示為：2（2（2+2（0）+2）+2（2（2+2（0）+2（2（2）+2（0）+2+2（0）解題思路：仔細(xì)觀察給出的幾個(gè)例子會發(fā)現(xiàn)，處理二進(jìn)制串的時(shí)候，遇到1就要進(jìn)行遞歸，1之間遇到0就要填+號，進(jìn)行遞歸時(shí)候要加括號，需要特判21,201. #include<cstdio> 

72、 2. #include<cstring>  3. #include<iostream>  4. #include<algorithm>  5. #include<cstdlib>  6. using namespace std;  7. void dfs(int n)  8.   9.     if(n=0) 

73、; 10.       11.         cout<<"0"  12.         return   13.       14.     string s; 

74、 15.     int num=n;  16.     while(num)  17.       18.         s+=num%2+'0'  19.         num/=2; 

75、 20.       21.     reverse(s.begin(),s.end();  22.     int flag=0;  23.     for(int i=0;i<s.length();i+)  24.       25.   

76、      if(si='1')  26.           27.             if(flag)  28.            

77、0;cout<<"+"  29.             flag=1;  30.             if(s.length()-i-1=1)  31.          

78、     32.                 cout<<"2"  33.               34.        

79、;     else  35.               36.                 cout<<"2"  37.     

80、            cout<<"("  38.                 dfs(s.length()-i-1);  39.          &

81、#160;      cout<<")"  40.               41.           42.       43.   44. int m

82、ain()  45.   46.     int num;  47.     cin>>num;  48.     string s;  49.     while(num)  50.       51.   

83、;      s+=num%2+'0'  52.         num/=2;  53.       54.     reverse(s.begin(),s.end();  55.     int flag=0; 

84、0;56.     for(int i=0;i<s.length();i+)  57.       58.         if(si='1')  59.           60.      &#

85、160;      if(flag)  61.             cout<<"+"  62.             flag=1;  63.     

86、0;       if(s.length()-i-1=1)  64.               65.                 cout<<"2"  

87、;66.               67.             else  68.               69.     

88、60;           cout<<"2"  70.                 cout<<"("  71.          

89、;       dfs(s.length()-i-1);  72.                 cout<<")"  73.               

90、74.               75.           76.       77.   7. 導(dǎo)彈攔截-動態(tài)規(guī)劃問題描述某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前

91、一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。解題思路：因?yàn)橐蠛竺婷恳话l(fā)炮彈都不能高于前一發(fā)，故問題就轉(zhuǎn)化成了求最長不下降子序列，用n2算法即可。對于第二問，遇到高于前一項(xiàng)的，便要準(zhǔn)備另外一套系統(tǒng)，而且要全部攔截，故求嚴(yán)格的最長上升子序列。dpi表示以i位置結(jié)束的最長不下降子序列；dpsi表示以i位置結(jié)束的最長上升子序列；注意初始化問題，對于每一個(gè)dpi，最少也會包括自

92、身，所以都要初始化為1；cpp view plaincopy1. #include<cstdio>  2. #include<cstring>  3. #include<algorithm>  4. #define max(a,b) (a)>(b)?(a):(b)  5. using namespace std;  6. int main()   7.  

93、 8.     int dp10010;  9.     int dps10010;  10.     memset(dp,0,sizeof(dp);  11.     memset(dps,0,sizeof(dps);  12.     int n=0;  

94、13.     int num10010;  14.     int x;  15.     while(scanf("%d",&x)  16.     num+n=x;  17.     for(int i=1;i<=n;i+)  1

95、8.     dpi=dpsi=1;  19.     for(int i=1;i<=n;i+)  20.       21.         for(int j=1;j<i;j+)  22.         

96、;  23.             if(numi<=numj)  24.               25.                

97、 dpi=max(dpi,dpj+1);  26.               27.             if(numi>numj)  28.            &

98、#160;  29.                 dpsi=max(dpsi,dpsj+1);  30.                31.         

99、60; 32.       33.     int ans1=0,ans2=0;  34.     for(int i=1;i<=n;i+)  35.       36.         ans1=max(ans1,dpi); 

100、60;37.         ans2=max(ans2,dpsi);  38.       39.     printf("%dn",ans1);  40.     printf("%dn",ans2);  41.   9. 藍(lán)橋杯 回文數(shù)問題描述若一個(gè)數(shù)（

101、首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數(shù)。例如：給定一個(gè)10進(jìn)制數(shù)56，將56加65（即把56從右向左讀），得到121是一個(gè)回文數(shù)。又如：對于10進(jìn)制數(shù)87：STEP1：87+78 = 165 STEP2：165+561 = 726STEP3：726+627 = 1353 STEP4：1353+3531 = 4884在這里的一步是指進(jìn)行了一次N進(jìn)制的加法，上例最少用了4步得到回文數(shù)4884。寫一個(gè)程序，給定一個(gè)N（2<=N<=10或N=16）進(jìn)制數(shù)M（其中16進(jìn)制數(shù)字為0-9與A-F），求最少經(jīng)過幾步可以得到回文數(shù)。如果在30步以內(nèi)（包含30步）不可能得到回

102、文數(shù)，則輸出“Impossible!”輸入格式兩行，N與M輸出格式如果能在30步以內(nèi)得到回文數(shù)，輸出“STEP=xx”（不含引號），其中xx是步數(shù)；否則輸出一行”Impossible!”（不含引號）樣例輸入987問題描述若一個(gè)數(shù)（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數(shù)。例如：給定一個(gè)10進(jìn)制數(shù)56，將56加65（即把56從右向左讀），得到121是一個(gè)回文數(shù)。又如：對于10進(jìn)制數(shù)87：STEP1：87+78 = 165 STEP2：165+561 = 726STEP3：726+627 = 1353 STEP4：1353+3531 = 4884在這里的一步是指進(jìn)行了一次N

103、進(jìn)制的加法，上例最少用了4步得到回文數(shù)4884。寫一個(gè)程序，給定一個(gè)N（2<=N<=10或N=16）進(jìn)制數(shù)M（其中16進(jìn)制數(shù)字為0-9與A-F），求最少經(jīng)過幾步可以得到回文數(shù)。如果在30步以內(nèi)（包含30步）不可能得到回文數(shù)，則輸出“Impossible!”輸入格式兩行，N與M輸出格式如果能在30步以內(nèi)得到回文數(shù)，輸出“STEP=xx”（不含引號），其中xx是步數(shù)；否則輸出一行”Impossible!”（不含引號）樣例輸入9871. #include<iostream>  2. #include<cmath>  3. #

104、include<algorithm>  4. using namespace std;  5. long long to10(int num,string s)  6.   7.     long long t=0;  8.     int len=s.length();  9.  &#

105、160;  if(num<=10)  10.       11.         int len=s.length();  12.         for(int i=0;i<len;i+)  13.      

106、60;    14.             if(si!='0')  15.               16.             &#

107、160;   t+=(si-'0')*pow(num,len-i-1);  17.               18.           19.       20.     else 

108、; 21.       22.         for(int i=0;i<len;i+)  23.           24.             if(si>'9'

109、)  25.               26.                 t+=(si-'A'+10)*pow(num,len-i-1);  27.        &

110、#160;      28.             else  29.               30.             

111、60;   t+=(si-'0')*pow(num,len-i-1);  31.               32.           33.       34.     return

112、0;t;  35.   36. bool judge(int num,long long t)  37.   38.     string s;  39.     while(t)  40.       41.       

113、60; int cur=t%num;  42.         t/=num;  43.         if(cur<=9)  44.           45.        &#

114、160;    s+=cur+'0'  46.           47.         else  48.           49.        

115、     s+=cur-10+'A'  50.           51.       52.     reverse(s.begin(),s.end();  53.     int len=s.length();  54.

116、     for(int i=0;i<len/2;i+)  55.       56.         if(si!=slen-1-i)  57.         return false;  58.     &#

117、160; 59.     return true;  60.   61. int main()  62.   63.     int num;  64.     string s;  65.     cin>>num>>s;  

118、;66.     int count=0;  67.     while(count<31)  68.       69.         count+;  70.         string ss=s;

119、0; 71.         reverse(ss.begin(),ss.end();  72.         long long t1=to10(num,s);  73.         long long t2=to10(num,ss);  7

120、4.         if(judge(num,t1+t2)  75.         break;  76.         s.clear();  77.         long long t=

121、t1+t2;  78.         while(t)  79.           80.             int cur=t%num;  81.       

122、;      t/=num;  82.             if(cur<=9)  83.               84.         

123、60;       s+=cur+'0'  85.               86.             else  87.        

124、;       88.                 s+=cur-10+'A'  89.               90.      &#

125、160;    91.         reverse(s.begin(),s.end();   92.       93.     if(count<31)  94.     cout<<"STEP="<<count<<end

126、l;  95.     else  96.     cout<<"Impossible!"<<endl;  97.   10. 旅行家的預(yù)算問題描述一個(gè)旅行家想駕駛汽車以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（假設(shè)出發(fā)時(shí)油箱是空的）。給定兩個(gè)城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發(fā)點(diǎn)每升汽油價(jià)格P和沿途油站數(shù)N（N可以為零），油站i離出發(fā)點(diǎn)的距離Di、每升汽

127、油價(jià)格Pi（i=1，2，N）。計(jì)算結(jié)果四舍五入至小數(shù)點(diǎn)后兩位。如果無法到達(dá)目的地，則輸出“No Solution”。輸入格式第一行為4個(gè)實(shí)數(shù)D1、C、D2、P與一個(gè)非負(fù)整數(shù)N；接下來N行，每行兩個(gè)實(shí)數(shù)Di、Pi。輸出格式如果可以到達(dá)目的地，輸出一個(gè)實(shí)數(shù)（四舍五入至小數(shù)點(diǎn)后兩位），表示最小費(fèi)用；否則輸出“No Solution”（不含引號）。樣例輸入275.6 11.9 27.4 2.8 2102.0 2.9220.0 2.2樣例輸出26.95解題思路：貪心規(guī)則：從當(dāng)前點(diǎn)開始，再c*d2的距離內(nèi)，找第一個(gè)油價(jià)低于當(dāng)前結(jié)點(diǎn)油價(jià)的站點(diǎn)如果找到：如果當(dāng)前結(jié)點(diǎn)剩余油量可以抵達(dá)，更新下一個(gè)站點(diǎn)的剩余油量；

128、如果當(dāng)前結(jié)點(diǎn)剩余油量不可以抵達(dá)，更新當(dāng)前結(jié)點(diǎn)需要添加的油量；如果找不到：則在本站加滿油，將相鄰的結(jié)點(diǎn)當(dāng)做下一個(gè)目的結(jié)點(diǎn)；-條件1如果超過c*d2，則不可以到達(dá)；需要注意的是：判斷找沒找到時(shí)候應(yīng)當(dāng)注意用目的結(jié)點(diǎn)與當(dāng)前結(jié)點(diǎn)的差值<c*d2,判斷。如果單單用一個(gè)flag標(biāo)志的話，當(dāng)遇到最后一個(gè)結(jié)點(diǎn)，即目的地，你會直接跳到-條件1-那個(gè)條件中，從而多加了油，使得結(jié)果偏大；cpp view plaincopy1. #include<cstdio>  2. #include<algorithm>  3. using 

129、namespace std;  4.   5. struct node  6.   7.     double dis;  8.     double cost;  9.     double has;  10.     double ad

130、d;  11.     int id;  12. ;  13.   14. int main()  15.   16.     /freopen("test.txt","r",stdin);  17.     double distance;  18.     double c;  19.     double v;  20.     double scost;  21.     int n;  22.     node sta10001;  23