18寒假最后一测+dijistra模板
| 題目名稱 | run | homework | cut |
| 輸入 | run.in | homework.in | cut.in |
| 輸出 | run.out | homework.out | cut.out |
| 每個測試點時限 | 1秒 | 1秒 | 2秒 |
| 內存限制 | 64MB | 64MB | 64MB |
| 測試點數目 | 10 | 10 | 10 |
| 每個測試點分值 | 10 | 10 | 10 |
| 是否有部分分 | 無 | 無 | 無 |
| 題目類型 | 傳統 | 傳統 | 傳統 |
?
run
Background:
??? ??? 穿過時空隧道，小明來到了秦朝。我是誰？我在哪？
????? ????? “哈哈哈，金科，發什么呆呢，你的刺殺已經失敗了!”秦王躲在柱子后狂妄的笑。
????? ????? 一股熱血在小明體內流動，他竟情不自禁地追了上去。
Description:
??? ??? 宮殿里一共有n根柱子，假設柱子在二維平面內的位置為（xi,yi）。金科現在在一號柱子，秦王現在在n號柱子。金科(小明)會飛檐走壁所以他從i號柱子到j號柱子的距離為min(|xi-xj|,|yi-yj|)。深知自己并不能刺殺秦王，所以小明知道事實上自己竭盡全力，也離秦王有一步之遙，所以小明想知道自己到達n號柱子的最短距離-1是多少，因為這將是他人生能走過的最后的路。
Input:
??? ??? 第一行一個數n。
????? ????? 接下來n-1行每行兩個數x,y分別表示xi和yi。
Output：
????? ????? 一行一個數表示從1號柱子走到n號柱子的最短距離減去1的長度。
Sample input:
5
2 2
1 1
4 5
7 1
6 7
Sample output:
1
Hint：
1->2->4->5最短距離為2，答案為1。
對于30%的數據，n<=1000。
對于100%的數據,n<=200000,0<xi,yi<1e9
數據保證答案>0，不然很奇怪。。
?題解：我們發現每個點分別于橫縱坐標相鄰的點連邊就可以解決問題了，建邊后直接跑最短路就可以了。最后不要忘記答案-1.（可以自己構圖驗證正確性）
?用堆優化+dijistra的板子
#include <bits/stdc++.h> #include <algorithm> using namespace std; #define maxn 200005 #define maxm 1000005 bool vis[maxn]; int L,n,tot,head[maxn],dis[maxn]; inline void read(int &x){x=0;int f=1;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}x*=f; } struct Point{int x,y,id; }p[maxn]; struct edge{int nxt,v,w; }G[maxm]; struct rp{int id,key;rp(int a,int b){id=a, key=b;} }; bool cmp2(Point a, Point b){return a.x < b.x; } bool cmp1(Point a, Point b){return a.y < b.y; } struct cmp{bool operator()(const rp& a, const rp& b){return a.key > b.key;} };void add(int u, int v, int w){G[++tot].nxt = head[u];G[tot].w = w;G[tot].v = v;head[u] = tot;G[++tot].nxt = head[v];G[tot].w = w;G[tot].v = u;head[v] = tot; } void dijistra(){memset(dis, 127, sizeof(dis));priority_queue <rp,vector<rp>,cmp> q;q.push(rp(1, 0));dis[1] = 0;while(!q.empty()){rp u = q.top();q.pop();if(vis[u.id])continue;vis[u.id] = 1;for(int j = head[u.id]; j; j = G[j].nxt){int v = G[j].v;if(dis[v] > dis[u.id] + G[j].w){dis[v] = dis[u.id] + G[j].w;q.push(rp(v, dis[v]));}}} } int main() { freopen("run.in","r",stdin);freopen("run.out","w",stdout);read(n);for(int i = 1; i <= n; i++)read(p[i].x), read(p[i].y), p[i].id = i;sort(p+1, p+1+n, cmp2);for(int i = 1; i < n; i++)add(p[i].id, p[i+1].id, p[i+1].x - p[i].x);sort(p+1, p+1+n, cmp1);for(int i = 1; i < n; i++)add(p[i].id, p[i+1].id, p[i+1].y - p[i].y);dijistra();printf("%d\n",dis[n]-1); }?
?
?
homework
Background:
??? ??? 小哪吒在開學前一天補作業。。。
Description:
??? ??? 明天就要開學了！所以小哪吒需要盡快寫完作業。現在，他有n份作業需要寫，因為小哪吒精通變化，他可以再變出兩只手來，所以他可以同時寫兩份作業。小哪吒兩雙手寫同一份作業的時間是不一樣的。為了節約時間，他用火眼睛睛看出了兩雙手寫同一份作業分別需要ai，bi的時間。同樣的，為了節約時間，他不會更改做題的順序，即他會從第一份作業一直做到第n份作業。他唯一不知道的是，他能寫完作業的最短時間。你能幫他求出來嗎？
Input:
??? ??? 第一行一個數n表示作業的數目。
????? ????? 接下來n行每行兩個數ai，bi分別表示小哪吒兩雙手寫這份作業的時間。
Output:
??? ??? 一行一個數表示寫作業的最短時間。
Sample input:
3
1 3
1 3
1 3
Sample output:
??? 3
Hint:
????? ????? 對于樣例，用第一雙手做完所有作業。
????? ????? 對于40%的數據,n<=20。
????? ????? 對于100%的數據,n<=2000。ai,bi<=3000。
?題解：我們用dp[i][0/1][j]表示去做第i份作業用第0/1只手時，另外一雙手還需要做j的時間才能做完作業的最小時間；
dp[i][j][k] = min( dp[i - 1][ j ][ k+a[i - 1][ j ] ] + a[i - 1][ j ], ?dp[i - 1][ j^1 ][ a[i - 1][ j^1 ] ] , 但我們有可能在0手有空時不一定用0手而是等1手完了用1手，
而這樣當?k+a[i - 1][ j ] ?= 0我們剛好就去用了空閑的手，故我們反著推就可以了，因為dp[i][j][k] k=0 時有可能那只手已經休息了很久了；
注意dp[i]中第i份作業還沒做，所以我們最后要加上剩下的時間
#include <bits/stdc++.h>using namespace std; #define maxn 2005 int dp[maxn][2][3005], a[maxn][2]; inline void read(int &x){x=0;int f=1;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}x*=f; }int main(){///freopen("homework.in","r",stdin);//freopen("homework.out","w",stdout);int n;read(n);for(int i = 1; i <= n; i++)read(a[i][0]), read(a[i][1]);memset(dp, 0x3f, sizeof(dp));dp[1][0][0] = dp[1][1][0] = 0;for(int i = 1; i <= n; i++)for(int j = 0; j < 2; j++)for(int k = 0; k <= 3000; k++){dp[i+1][j][max(0, k-a[i][j])] = min(dp[i+1][j][max(0, k-a[i][j])], dp[i][j][k]+a[i][j]);dp[i+1][j][max(0, a[i][j^1]-k)] = min(dp[i+1][j][max(0, a[i][j^1]-k)] , dp[i][j^1][k]+k);}int ans = 1e9;for(int j = 0; j < 2; j++)for(int k = 0; k <= 3000; k++)ans = min(ans, dp[n][j][k] + max(k, a[n][j]));printf("%d\n",ans); }?
cut
Background:
??? ??? 伐木工Zxr非常懶惰了，所以他在伐木的時候只會找準木頭被蟲蛀過的腐朽的地方砍下去。
Description：
??? ??? 一塊有N-1處被蟲蛀過的地方，假設被蟲蛀過的地方長度不計。這n-1個蟲蛀將木頭分成了n塊，題目將依次給出這n塊木頭的長度。懶惰的zxr最多只想砍m次，并且希望可以借此把這塊木頭分得盡量均勻，即希望使砍伐后連續的木塊中最長的盡量短。這個時候聰明的你跳了出來“我不僅能算出這個最短長度，我還能算出方案數！”
Input:
????? ????? 第一行兩個數n,m。
????? ????? 接下來一行n個數分別表示這N塊木頭的長度。
Output：
????? ????? 一行兩個數分別表示最短的最長長度和方案數。
Sampleinput：
????? ????? 3 2
????? ????? 1 1 10
Sampleoutput：
????? ????? 10 2
Hint：
????? ????? 兩種砍的方法: (1)(1)(10)和(1 1)(10)。
????? ????? 對于30%的數據,n<=10，
????? ????? 對于100%的數據，n<=50000,
0<=m<=min(n-1,1000),1<=Li<=1000.
題解：
第一問是一個十分顯然的二分，貪心Check()，很容易就能求出最小的最大長度 Len 。
第二問求方案總數，使用 DP 求解。
使用前綴和，令 Sum[i] 為前i根木棍的長度和。
令 f[i][j] 為前i根木棍中切 j 刀，并且滿足最長長度不超過 Len的方案數，那么：
狀態轉移方程： f[i][j] = Σ f[k][j-1] ((1 <= k <= i-1) && ?(Sum[i] - Sum[k] <= Len))
這樣的空間復雜度為 O(nm) ，時間復雜度為 O(n^2 m) 。顯然都超出了限制。
下面我們考慮 DP 的優化。
1) 對于空間的優化。
這個比較顯然，由于當前的 f[][j] 只與 f[][j-1] 有關，所以可以用滾動數組來實現。
f[i][Now] 代替了 f[i][j] ， f[i][Now^1] 代替了 f[i][j-1] 。為了方便，我們把 f[][Now^1] 叫做 f[][Last] 。
這樣空間復雜度為 O(n) 。滿足空間限制。
2) 對于時間的優化。
考慮優化狀態轉移的過程。
對于 f[i][Now] ，其實是 f[mink][Last]...f[i-1][Last] 這一段 f[k][Last] 的和，mink 是滿足 Sum[i] - Sum[k] <= Len 的最小的 k ，那么，對于從 1 到 n 枚舉的i，相對應的 mink 也一定是非遞減的（因為 Sum[i] 是遞增的）。我們記錄下 f[1][Last]...f[i-1][Last] 的和Sumf，mink 初始設為 1，每次對于i將 mink 向后推移，推移的同時將被舍棄的 p 對應的 f[p][Last] 從Sumf中減去。那么 f[i][Now] 就是Sumf的值。
這樣時間復雜度為 O(nm) 。滿足時間限制。
#include <bits/stdc++.h>using namespace std; #define maxn 50005 #define mod 10007 int dp[maxn][2], a[maxn], sum[maxn], L, n, m, Ml; inline void read(int &x){x=0;int f=1;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}x*=f; }bool check(int mid){int ll = 0, i = 0, group = 1, flag = 0;while(i <= n){if(ll + a[++i] <= mid)ll += a[i];else if(a[i] > mid)return false;else {group++;if(group > m + 1)return false;ll = a[i];}}return true; } void bs(){int l = Ml, r = sum[n];while(l != r){int mid = (l + r) >> 1;if(check(mid))r = mid;else l = mid+1;}L = r;//取大的printf("%d ",L); } void Dp(){int sumf = 0, mink = 0, ans = 0;int k = 0;for(int j = 0; j <= m; j++){sumf = 0; mink = 1;//一定要記得更新，忘了更新這個地方，WA了好多次for(int i = 1; i <= n; i++){if(!j){if(sum[i] <= L)dp[i][k] = 1;}else {while(mink < i && sum[i] - sum[mink] > L){sumf -= dp[mink][k^1];sumf = (sumf + mod) % mod;mink++; } dp[i][k] = sumf;} sumf = (sumf + dp[i][k^1]) % mod;}ans += dp[n][k];ans %= mod;k^=1;//滾動數組 }printf("%d\n",ans); } int main(){freopen("cut.in","r",stdin);freopen("cut.out","w",stdout);read(n),read(m);for(int i = 1; i <= n; i++){read(a[i]);Ml = max(Ml, a[i]);sum[i] = sum[i-1] + a[i];}bs();Dp(); }?
轉載于:https://www.cnblogs.com/EdSheeran/p/8496929.html
總結
以上是生活随笔為你收集整理的18寒假最后一测+dijistra模板的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： network programming-
- 下一篇： jquery监听滚动条