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