鐵塔
(tower.pas/c/cpp)
題目描述
Rainbow 和Freda 要在Poetic Island 市的一座山腳下蓋房子定居了……蓋房子需要鋼材

，幸運的是，這里有排成一行的n 座廢棄的鐵塔，從左到右編號為1~n，其中第i 座的高度為h[i]。

Rainbow 和Freda 想蓋一座上面小下面大的城堡，并且城堡的層數盡可能多。

因此，他們要把這些鐵塔分成盡量多組，每組內的鐵塔編號必須是連續的，并且從左到右各組內鐵塔的高度之和單調不減。

最后，他們會用每組鐵塔所提供的鋼材構成一層城堡。但是 Rainbow 和Freda 簡直弱爆了有木有，

于是請你幫忙計算一下最多能分成多少組呢？

?

輸入格式
第一行一個整數n。

第二行 n 個整數，第i 個整數表示h[i]。

輸出格式

輸出一個整數，表示(n - 最多能分成的組數)。

?

這道題一開始我還以為是貪心 結果后來貪心是錯的 然后就突然想到了dp是怎么搞的

然后dp[i]表示以1 ~ i 并且以第i個結尾的一段最多分為多少組

len[i]表示dp[i]對應的最后一組的高度之和是多少 維護一個前綴和

轉移就是dp[i] = dp[j] + 1 (sum[i] - sum[j]) 表示j + 1 ~ i 分成一組

然后如果相等取len的min方便后面轉移

代碼

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <cmath> using namespace std;typedef long long ll; const int N = 5000 + 10; int n; ll h[N],dp[N],len[N],sum[N];int main( ) {freopen("tower.in","r",stdin);freopen("tower.out","w",stdout);scanf("%d",& n);for(int i = 1;i <= n;i ++) {scanf("%I64d",& h[i]);sum[i] = sum[i - 1] + h[i];}for(int i = 1;i <= n;i ++)for(int j = 0;j < i;j ++) {if(sum[i] - sum[j] >= len[j]) {if(dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1;len[i] = sum[i] - sum[j];}else if(dp[j] + 1 == dp[i]) {len[i] = min(len[i],sum[i] - sum[j]);}}}printf("%I64d",n - dp[n]); }

工作計劃

(work.pas/c/cpp)

題目描述

Mark 在無意中了解到了 Elf 的身世。在和 James 商量過之后，好心的他們打算送 Elf 返回故鄉。

然而，去往 Gliese 的飛船票價高的驚人，他們暫時還付不起這筆費用。經過一番考慮，Mark 打算去額外做一些工作來獲得收入。

經過一番調查，Mark 發現有 N 個工作可以做。做第 i 件工作所需要的時間為 Di，同時也需要一個能力值 Ci 才可以去做，

每件工作都可以在任意時間開始，也可以做任意多次。所有的工作給付的報酬都是一致的。同時，有 S 個課程可以參加，

我們認為今天是第 0 天，第 i 個課程在第 Mi 天開始，持續時間為 Li 天，課程結束之后能力值會變為 Ai。現在 Mark 的能力值為 1。

Mark 只能做工作到第 T 天（因為那是飛船起飛的日子）。

他想知道期限內他最多可以做多少件工作，好決定未來的打算。于是他找到你了 applepi。

でも、applepi は彼女と一緒に楽しむことが大切だ，所以這個任務就交給你了。

?

輸入格式

第一行包含三個空格分隔的整數 T,S,N。

之后 S 行，每行三個整數 M,L,A，描述一個課程。

之后 N 行，每行兩個整數 C,D，描述一件工作。

?

輸出格式

一個整數，表示 Mark 最多可以做多少件工作。

?

這道題正解是dp 我復制一波題解

動態規劃，定義f[i][j]代表在i時間，能力值為j的最多工作次數。

對應最后三種選擇：

①不作為 f[i][j]=f[i-1][j],

②上課 f[i][j]=f[上課前一個時刻][任意],

③做工作 f[i][j]=f[i-po[j]][j]+1 （po[j]為能力值<=j的工作一次的最短用時）。

對于②可以在預處理出ke[i][j]在i時刻結束，能力值達到j的課程的最晚開始時間。dp過程中處理出g[i]=max{f[i][j]}。

g[t]即為答案。

然后考試的時候我寫的搜索竟然A了... 我也不知道我那個復雜度是多少 就很迷

dp代碼(yyyuuudalao的)

#include <cstdio> #include <algorithm> using namespace std ; int dp[10005][105] ; int Day ; int N , M ; int mnn[105] ; int zjj[10005][105] ; int fz[10005] ; int main ( ) {freopen ( "wrk.in" , "r" , stdin ) ; freopen ( "wrk.out" , "w" , stdout ) ; scanf ( "%d%d%d" , &Day , &M , &N ) ;for ( int i = 0 ; i <= Day ; i++ )for ( int j = 1 ; j <= 100 ; j++ ) zjj[i][j] = 1e9 ; for ( int i = 1 ; i <= M ; i++ ){int s , l , u ; scanf ( "%d%d%d" , &s , &l , &u ) ; zjj[s+l][u] = min ( zjj[s+l][u] , l ) ; } for ( int i = 0 ; i <= 100 ; i++ ) mnn[i] = 1e9 ; for ( int i = 1 ; i <= N ; i++ ) {int s , t ; scanf ( "%d%d" , &s , &t ) ; mnn[s] = min ( mnn[s] , t ) ; }for ( int i = 1 ; i <= 100 ; i++ ) mnn[i] = min ( mnn[i] , mnn[i-1] ) ;for ( int i = 0 ; i <= Day ; i++ ) for ( int j = 1 ; j <= 100 ; j++ ) dp[i][j] = -1e9 ; dp[0][1] = 0 ; for ( int i = 1 ; i <= Day ; i++ ) {for ( int j = 1 ; j <= 100 ; j++ ){dp[i][j] = dp[i-1][j] ; if ( zjj[i][j] != 1e9 ) dp[i][j] = max ( dp[i][j] , fz[i-zjj[i][j]] ) ; if ( i - mnn[j] >= 0 ) dp[i][j] = max ( dp[i][j] , dp[i-mnn[j]][j] + 1 ) ; fz[i] = max ( fz[i] , dp[i][j] ) ; }} printf ( "%d\n" , fz[Day] ) ; }

蒟蒻的垃圾搜索代碼

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <cmath> using namespace std;const int N = 100 + 5; const int M = 1e5 + 5; int t,s,n,mi[N],ans; bool vis[M],name[M]; struct node {int tim;bool operator < (const node & a) const {return tim > a.tim;} }; int w[N];struct lesson{int st,len,abi; }l[N];void dfs(int day,int abil,int min_tim,int wrk) {if(day == t + 1) {ans = max(ans,wrk); return ;}else if(day > t + 1) {ans = max(ans,wrk - 1); return ;}int mm = min_tim;if(vis[day]) {int id = name[day]; bool tag = false;int cmp = max(abil,l[id].abi);if(cmp == abil) tag = true;if(! tag) {min_tim = mi[cmp];dfs(day + l[id].len,cmp,min_tim,wrk);}}dfs(day + min_tim,abil,mm,wrk + 1); }int main( ) {freopen("wrk.in","r",stdin);freopen("wrk.out","w",stdout);scanf("%d%d%d",& t,& s,& n);for(int i = 1;i <= s;i ++) {scanf("%d%d%d",& l[i].st,& l[i].len,& l[i].abi);l[i].st ++; name[l[i].st] = i;vis[l[i].st] = true;}memset(w,0x3f3f3f,sizeof(w));for(int i = 1;i <= n;i ++) {int cc,tt;scanf("%d%d",& cc,& tt);w[cc] = min(w[cc],tt);}memset(mi,0x3f3f3f,sizeof(mi));for(int i = 1;i <= 100;i ++)for(int j = 1;j <= i;j ++)if(w[j] != 0) mi[i] = min(mi[i],w[j]);dfs(1,1,mi[1],0);printf("%d",ans); }

樹洞
(holes.pas/c/cpp)
題目描述
在一片棲息地上有N棵樹 ，每棵樹下住著一只兔子 ，有 M條路徑連接這些樹。

更特殊地是，只有一棵樹有3條或更多的路徑與它相連，其它樹只有1條或2條路徑與它相連，

換句話講，這些樹和之間的構成一張 N個點、 M條邊的無向連通圖，而度數大于2的點至多有1個。

近年以來 ，棲息地頻繁受到人類的侵擾。兔子們聯合起來召開了一場會議， 決定在其中K棵樹上建造洞。

當危險來臨時，每只兔子均會同時前往距離最近的樹洞躲避 ，路程中花費的時間在數值上等于距離。

為了在最短的時間內讓所有兔子脫離危險，請你安排一種建造樹洞的方式使最后一只到達樹洞的兔子所花費的時間盡量少。

?

輸入格式

第一行有 3個整數 N，M，K，分別表示樹（兔子） 的個數 、路徑數計劃 建造的樹洞數 。

接下來 M行每三個整數 x,y，表示第x棵樹和第y棵樹之間有一條路徑相連。1<=x,y<=N，x≠y，任意兩棵樹之間至多只有1條路徑。

?

輸出格式

一個整數，表示在最優方案下后只到達樹洞的兔子所花費時間 。

?

這道題還是挺難的 至少我在考試的時候并沒有任何思路 然后下來聽大佬們講才懂得

這道題因為度數大于二的 點只有一個 所以他可以形成一個菊花（buhsi）圖

一旦把菊花心給他割了(......??????? 剩下的東西肯定是幾條鏈...

所以就二分最短的最長長度 也就是最后一只兔賊到樹洞的時間

如何搞呢 就是先把菊花心在二分的長度內可以走到的點都打上標記

然后把剩下的鏈長度dfs搞一搞 對于每條鏈 他的需要的洞數量就是 鏈的長度 / (二分答案 * 2 + 1)

因為分母就是貪心的每一個洞覆蓋的最長長度 然后這玩意兒要上取整

然而會出現最優方案并不會選到菊花心的問題 那么怎么搞呢 枚舉菊花心可以走到的點

每次去選一選 就像上述一樣搞一搞就可以了?

正確性是因為在這個范圍內選的數 對于它的覆蓋范圍內的點都打上標記 剩下的仍然是若干條連

然而為什么一定要在范圍內選呢 因為如果不在范圍內選 菊花心就選不到就不合法了

然后剩下的情況就是沒有菊花心 就是一條鏈

那就是(n - k) / (2 * k) 就是n個點里面選了剩下的點除以每個點覆蓋范圍上取整

?

代碼(我調了特別久就是因為bfs里面起點沒打標記 我恨...!!!!!)

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <cmath> #define oo 1000000000 using namespace std;const int N = 2000 + 5; int n,m,k,now,rd[N],tot,head[N],nex[N * N],tov[N * N]; int dis[N][N],root; bool vis[N]; queue<int>Q;void add(int u,int v) {tot ++;tov[tot] = v;nex[tot] = head[u];head[u] = tot; }void bfs(int u) {memset(vis,0,sizeof(vis));Q.push(u);vis[u] = true;while(! Q.empty( )) {int x = Q.front( );Q.pop( );for(int i = head[x];i;i = nex[i]) {int v = tov[i];if(! vis[v]) {vis[v] = true; Q.push(v);dis[u][v] = dis[v][u] = dis[u][x] + 1;}}} }void dfs(int u) {now ++; vis[u] = true;for(int i = head[u];i;i = nex[i]) {int v = tov[i];if(! vis[v]) dfs(v);} }int solve(int u,int len) {int ans = 0;memset(vis,0,sizeof(vis));for(int i = 1;i <= n;i ++)if(dis[u][i] <= len) vis[i] = true;for(int i = 1;i <= n;i ++)if(! vis[i]) {now = 0;dfs(i);ans += ceil(1.0 * now / (2 * len + 1));}return ans; }bool check(int len) {int aaa = oo;for(int i = 1;i <= n;i ++)if(dis[root][i] <= len) aaa = min(aaa,solve(i,len));int fuck=0;if(aaa + 1<= k) fuck=1;return fuck; }int main( ) {freopen("holes.in","r",stdin);freopen("holes.out","w",stdout);scanf("%d%d%d",& n,& m,& k);for(int i = 1;i <= m;i ++) {int u,v;scanf("%d%d",& u,& v);add(u,v); add(v,u);rd[u] ++; rd[v] ++;}for(int i = 1;i <= n;i ++) {bfs(i); if(rd[i] > 2) root = i;}if(! root) root = 1;int l = 1,r = n,ans = -1;while(l <= r) {int mid = (l + r) >> 1;if(check(mid)) ans = mid,r = mid - 1;else l = mid + 1;}cout << ans; }

今天考的還可以..

轉載于:https://www.cnblogs.com/Rubenisveryhandsome/p/9506823.html

總結

以上是生活随笔為你收集整理的18.8.20 考试总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。