1 第一題?小Q系列故事——屌絲的逆襲

　　表示這道題基本沒(méi)什么算法，學(xué)過(guò)計(jì)算機(jī)語(yǔ)言的應(yīng)該都能搞定吧。

2 第二題?小明系列故事——買(mǎi)年貨

　　這道題直接用01背包問(wèn)題就可以解決了，只是除了錢(qián)的限制，還有積分的限制和免費(fèi)的情況，就是這點(diǎn)在調(diào)試程序的時(shí)候出了點(diǎn)小問(wèn)題，總是wa。狀態(tài)可以定義為dp[x][y][z]，x表示錢(qián)的，y表示積分的，z表示免費(fèi)的狀態(tài)，然后其它的和背包問(wèn)題差不多了，只是維數(shù)到了3維。

1 #include <stdio.h> 2 #include <string.h> 3 4 #define max(a,b) a > b ? a : b 5 int n, v1, v2, k; 6 typedef struct _thing 7 { 8 int a; 9 int b; 10 int val; 11 }thing_t; 12 13 int main(void) 14 { 15 thing_t data[101]; 16 int ans; 17 int dp[101][101][6]; 18 int i,j,y,x, temp; 19 while (scanf("%d%d%d%d", &n, &v1, &v2, &k) != EOF) 20 { 21 for (i = 1; i <= n; i ++) 22 scanf("%d%d%d", &data[i].a, &data[i].b, &data[i].val); 23 memset(dp, -1, sizeof(dp)); 24 ans = 0; 25 dp[0][0][0] = 0; 26 for (i = 1; i <= n; i ++) 27 { 28 for (j = v1; j >= 0; j --) 29 { 30 for (y = v2; y >= 0; y --) 31 { 32 for (x = k; x >= 0; x --) 33 { 34 temp = -1; 35 if (j - data[i].a >= 0 && dp[j - data[i].a][y][x] != -1) 36 { 37 if( temp < dp[j - data[i].a][y][x] + data[i].val)38 temp = dp[j - data[i].a][y][x] + data[i].val; 39 } 40 if (y - data[i].b >= 0 && dp[j][y - data[i].b][x] != -1) 41 { 42 if( temp < dp[j][y - data[i].b][x] + data[i].val) 43 temp = dp[j][y - data[i].b][x] + data[i].val; 44 } 45 if (x - 1 >= 0 && dp[j][y][x - 1] != -1) 46 { 47 if( temp < dp[j][y][x - 1] + data[i].val) 48 temp = dp[j][y][x - 1] + data[i].val; 49 } 50 dp[j][y][x] = max(temp, dp[j][y][x]); 51 if (ans < dp[j][y][x]) 52 ans = dp[j][y][x]; 53 } 54 } 55 } 56 } 57 printf("%d\n", ans); 58 } 59 return 0; 60 }

3 第三題?吉哥系列故事——臨時(shí)工計(jì)劃

　　這個(gè)題目就直接用dp了，dp[x]表示前x天內(nèi)獲得的最大工資數(shù)，狀態(tài)方程為：

　　dp[x] = max{dp[y] + c[y + 1][x]} ，其中c[y + 1][x]表示某份從第y + 1天到第x天的工作的工資，1 <= y <= x - 1 且?c[y + 1][x]不為0。

1 #include <stdio.h> 2 #include <string.h> 3 4 int t; 5 int m,n; 6 int data[101][101]; 7 int ans[101]; 8 9 int main(void) 10 { 11 int i, j, k, s, e, c; 12 scanf("%d", &t); 13 for (i = 1; i <= t; i ++) 14 { 15 scanf("%d%d", &m, &n); 16 memset(data, 0 ,sizeof(data)); 17 for (j = 1; j <= n; j ++) 18 { 19 scanf("%d%d%d", &s, &e, &c); 20 if (data[s][e] < c) 21 data[s][e] = c; 22 } 23 ans[0] = 0; 24 for (j = 1; j <= m; j ++) 25 { 26 ans[j] = ans[j - 1]; 27 for (k = 1; k <= j; k ++) 28 if (data[k][j] && ans[k - 1] + data[k][j] > ans[j]) 29 ans[j] = ans[k - 1] + data[k][j]; 30 } 31 printf("%d\n", ans[m]); 32 } 33 return 0; 34 }

4?湫湫系列故事——植樹(shù)節(jié)

　　思路:根據(jù)題目選的3個(gè)人互不認(rèn)識(shí)或者都認(rèn)識(shí)則關(guān)系相同,從這種關(guān)系相同的反面來(lái)看就是3個(gè)人只有兩個(gè)認(rèn)識(shí)，最后一個(gè)人不認(rèn)識(shí),所以可以求這種反面情況的個(gè)數(shù),對(duì)于第i個(gè)人，可以選他自己和他的朋友一個(gè)即a中情況，剩余一個(gè)人選他不認(rèn)識(shí)的人(即非朋友)即n-a-1中情況，所以sum +=a*(n-a-1),sum表示總情況數(shù)，由于自己和朋友計(jì)算的時(shí)候會(huì)多算一次，所以最后要sum /= 2才是反面的情況總數(shù)。

1 #include <stdio.h> 2 3 int main(void) 4 { 5 int t, n, b, i, j, all; 6 double sum; 7 8 scanf("%d", &t); 9 for (i = 0; i < t; i ++) 10 { 11 scanf("%d", &n); 12 all = n * (n - 1) * (n - 2) / 6; 13 sum = 0.0; 14 for (j = 0; j < n; j ++) 15 { 16 scanf("%d", &b); 17 sum += b * (n - b - 1); 18 } 19 sum /= 2; 20 sum /= all; 21 printf("%.3lf\n", 1 - sum); 22 } 23 return 0; 24 }

5?威威貓系列故事——籃球夢(mèng)

　　首先算出B隊(duì)最終的得分sb，再算出要贏B隊(duì)至少要得的分sum = sb + 1 - a(a為A隊(duì)當(dāng)前的得分)，然后窮舉滿足后面得分不小于sum的所有情況。

1 #include <stdio.h> 2 3 int a, b, t; 4 __int64 ans; 5 int sum; 6 7 __int64 f(int start) /*計(jì)算階乘*/ 8 { 9 __int64 ans = 1; 10 11 while (start > 1) 12 { 13 ans *= start; 14 start --; 15 } 16 return ans; 17 } 18 19 int main(void) 20 { 21 int i,j; 22 long long c_w, c_d; 23 24 while (scanf("%d%d%d", &a, &b, &t) != EOF) 25 { 26 c_w = t / 15; 27 if (c_w % 2 == 0) 28 c_w = t / 30; 29 else 30 c_w = t / 30 + 1; 31 c_d = t / 30; 32 sum = b + c_d + 1 - a; 33 ans = 0; 34 for (i = 0; i <= c_w; i ++) 35 for (j = 0; j <= c_w - i; j ++) 36 if (i * 1 + j * 2 + (c_w - i - j) * 3 >= sum) 37 ans += f(c_w) / (f(i) * f(j) * f(c_w - i - j)); 38 printf("%I64d\n", ans); 39 } 40 return 0; 41 }

總結(jié)

以上是生活随笔為你收集整理的2013腾讯编程马拉松初赛（3月20日）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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