.net做網(wǎng)站用什么框架網(wǎng)絡(luò)營(yíng)銷模式有哪些?
最長(zhǎng)公共子序列
時(shí)間限制：1 sec
空間限制：256 MB
問(wèn)題描述
給定兩個(gè) 1 到 n 的排列 A,B （即長(zhǎng)度為 n 的序列，其中 [1,n] 之間的所有數(shù)都出現(xiàn)了恰好一次）。
求它們的最長(zhǎng)公共子序列長(zhǎng)度。
輸入格式
第一行一個(gè)整數(shù) n ，意義見(jiàn)題目描述。
第二行 n 個(gè)用空格隔開的正整數(shù) A[1],…,A[n]，描述排列 A。
第三行 n 個(gè)用空格隔開的正整數(shù) B[1],…,B[n]，描述排列 B。
輸出格式
一行一個(gè)整數(shù)，表示 A,B 的最長(zhǎng)公共子序列的長(zhǎng)度。
樣例輸入
5
1 2 4 3 5
5 2 3 4 1
樣例輸出
2
樣例解釋
(2,3) 和 (2,4) 都可以是這兩個(gè)序列的最長(zhǎng)公共子序列。
數(shù)據(jù)范圍
對(duì)于 80% 的數(shù)據(jù)，保證 n<=5,000。
對(duì)于 100% 的數(shù)據(jù)，保證 n<=50,000。
提示
[把 A 中的所有數(shù)替換成其在 B 中出現(xiàn)的位置，想一想，新序列的最長(zhǎng)上升子序列和所求的東西有什么關(guān)系呢？]
代碼實(shí)現(xiàn)?
def cal_loc():for i in range(1, n + 1):loc[b[i]] = idef lis():a[1] = b[1]k = 1for i in range(2, n + 1):if a[k] < b[i]:k += 1a[k] = b[i]else:l, r = 1, kwhile l <= r:mid = (l + r) // 2if a[mid] < b[i]:l = mid + 1else:r = mid - 1a[l] = b[i]return kn = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
loc = [0] * (n + 1)cal_loc()for i in range(1, n + 1):b[i] = loc[a[i]]print(lis())倒水問(wèn)題
時(shí)間限制：10 sec
空間限制：256 MB
問(wèn)題描述
鄧?yán)蠋熡杏?2 個(gè)容量分別為 n 單位、m 單位的沒(méi)有刻度的杯子。初始，它們都是空的。
鄧?yán)蠋熃o了你 t 分鐘時(shí)間。每一分鐘，他都可以做下面 4 件事中的任意一件：
- 用水龍頭裝滿一個(gè)杯子。
- 倒空一個(gè)杯子。
- 把一個(gè)杯子里的水倒到另一個(gè)杯子里，直到一個(gè)杯子空了或者另一個(gè)杯子滿了。
- 什么都不做。
鄧?yán)蠋熛Ｍ詈竽塬@得 d 個(gè)單位的水，假設(shè)最后兩個(gè)杯具中水量的總和為 x，那么鄧?yán)蠋煹牟粷M意度就為 |d-x|。
你希望鄧?yán)蠋煴M可能地滿意，于是請(qǐng)你計(jì)算鄧?yán)蠋煹牟粷M意度最小是多少。
輸入格式
一行 4 個(gè)整數(shù) n,m,t,d，分別表示兩個(gè)杯具的容量、時(shí)間限制、以及鄧?yán)蠋煹钠谕怠?/p>
輸出格式
一行一個(gè)整數(shù)，表示鄧?yán)蠋熥钚〉牟粷M意度。
樣例輸入
7 25 2 16
樣例輸出
9
樣例解釋
你可以在第 1 分鐘用水龍頭裝滿任意一個(gè)杯子，并在第 2 分鐘什么都不做，即可讓鄧?yán)蠋煹牟粷M意度為 9。
可以證明不存在更優(yōu)的解。
數(shù)據(jù)范圍
本題共設(shè)置 16 個(gè)測(cè)試點(diǎn)。
對(duì)于前 1 個(gè)測(cè)試點(diǎn)，保證 t=1。
對(duì)于前 2 個(gè)測(cè)試點(diǎn)，保證 t<=2。
對(duì)于前 4 個(gè)測(cè)試點(diǎn)，保證 t<=4。
對(duì)于前 10 個(gè)測(cè)試點(diǎn)，保證 1<=n,m<=100，1<=t<=100，1<=d<=200。
對(duì)于所有的 16 個(gè)測(cè)試點(diǎn)，保證 1<=n,m<=2,000，1<=t<=200，1<=d<=4,000。
代碼實(shí)現(xiàn)?
奶牛吃草
時(shí)間限制：4 sec
空間限制：256 MB
問(wèn)題描述
有一只奶牛在一條筆直的道路上（可以看做是一個(gè)數(shù)軸）。初始，它在道路上坐標(biāo)為 K 的地方。
這條道路上有 n 棵非常新鮮的青草（編號(hào)從 1 開始）。其中第 i 棵青草位于道路上坐標(biāo)為 x[i] 的地方。貝西每秒鐘可以沿著道路的方向向前（坐標(biāo)加）或向后（坐標(biāo)減）移動(dòng)一個(gè)坐標(biāo)單位的距離。
它只要移動(dòng)到青草所在的地方，就可以一口吞掉青草，它的食速很快，吃草的時(shí)間可以不計(jì)。
它要吃光所有的青草。不過(guò)，青草太新鮮了，在被吞掉之前，暴露在道路上的每棵青草每秒種都會(huì)損失一單位的口感。
請(qǐng)你幫它計(jì)算，該怎樣來(lái)回跑動(dòng)，才能在口感損失之和最小的情況下吃掉所有的青草。
輸入格式
第一行兩個(gè)用空格隔開的整數(shù) n,k，分別表示青草的數(shù)目和奶牛的初始坐標(biāo)。
第 2 行到第 n+1 行，第 i+1 行有一個(gè)整數(shù) x[i]，描述第 i 棵青草的坐標(biāo)。
輸出格式
一行一個(gè)整數(shù)，表示吃掉所有青草的前提下，最小損失的口感之和。保證答案在 32 位有符號(hào)整數(shù)的范圍內(nèi)。
樣例輸入
4 10
1
9
11
19
樣例輸出
44
樣例解釋
先跑到 9，然后跑到 11，再跑到 19，最后到 1，可以讓損失的口感總和為 29+1+3+11=44?？梢宰C明不存在比這更優(yōu)的解。
數(shù)據(jù)范圍
對(duì)于 50% 的數(shù)據(jù)，保證 1≤n≤4，1≤k,x[i]≤20。 對(duì)于 80% 的數(shù)據(jù)，保證 1≤n≤100。 對(duì)于 100% 的數(shù)據(jù)，保證 1≤n≤1000，1≤k,x[i]≤10^6。
提示
[我們先從另一個(gè)角度看答案，即損失的總口感：從初始狀態(tài)到奶牛吃掉第 1 棵草之間的時(shí)間（我們?cè)谙旅姘阉凶龅?1 段時(shí)間），所有的 n 棵青草都在流失口感；……；從奶牛吃掉第 i 棵草到它吃掉第 i+1 棵草之間的時(shí)間（我們?cè)谙旅姘阉凶龅?i+1 段時(shí)間），還沒(méi)有被吃掉的 n-i 棵草都在流失口感；……]
[于是我們發(fā)現(xiàn)，第 i 段時(shí)間對(duì)答案的貢獻(xiàn)，為這段時(shí)間的長(zhǎng)度與 n-i+1 的乘積。]
[接著，我們?cè)賮?lái)關(guān)注最優(yōu)策略。吃完一棵草后（包括初始時(shí)），奶牛的最優(yōu)策略一定是直奔另一棵草。]
[由于奶牛不會(huì)飛，所以奶牛走過(guò)的所有路一定是一段連續(xù)的區(qū)間。]
[顯然地，被奶牛經(jīng)過(guò)過(guò)的地方，按最優(yōu)策略，一定不會(huì)留下青草。]
[所以我們可以**將所有青草的坐標(biāo)排序**（下面我們都使用排完序后的編號(hào)），然后用 dp[l][r][j] 表示吃完 [l,r] 范圍內(nèi)的青草時(shí)的最小答案，j 只有 0,1 兩種取值，分別表示奶牛吃完最后一棵草停在青草 l 還是 r 上（只有可能是這兩種情況，否則與上面的結(jié)論矛盾）。]
[于是我們就可以輕易地設(shè)計(jì)出狀態(tài)轉(zhuǎn)移方程：]
[dp[l][r][0]=min(dp[l+1][r][0]+(n-r+l)*abs(x[l]-x[l+1]),dp[l+1][r][1]+(n-r+l)*abs(x[l]-x[r]))]
[dp[l][r][1]=min(dp[l][r-1][1]+(n-r+l)*abs(x[r]-x[r-1]),dp[l][r-1][0]+(n-r+l)*abs(x[r]-x[l]))]
[邊界為：dp[i][i][j]=abs(x[i]-k)*n（對(duì)于所有1<=i<=n，j=0,1）]
[友情提示：請(qǐng)注意枚舉順序。]
代碼實(shí)現(xiàn)
def min_taste_loss(n, k, x):INF = float('inf')dp = [[[INF for _ in range(2)] for _ in range(n + 1)] for _ in range(n + 1)]# Base casefor i in range(1, n + 1):dp[i][i][0] = dp[i][i][1] = abs(x[i] - k) * n# Dynamic programmingfor length in range(2, n + 1):for l in range(1, n - length + 2):r = l + length - 1dp[l][r][0] = min(dp[l + 1][r][0] + (n - r + l) * abs(x[l] - x[l + 1]),dp[l + 1][r][1] + (n - r + l) * abs(x[l] - x[r]))dp[l][r][1] = min(dp[l][r - 1][1] + (n - r + l) * abs(x[r] - x[r - 1]),dp[l][r - 1][0] + (n - r + l) * abs(x[r] - x[l]))return min(dp[1][n][0], dp[1][n][1])# 讀取輸入
n, k = map(int, input().split())
x = [0] + [int(input()) for _ in range(n)] # 青草的坐標(biāo)，下標(biāo)從1開始# 排序青草的坐標(biāo)
x.sort()# 輸出結(jié)果
result = min_taste_loss(n, k, x)
print(result)