HiHi 的 Blog
0%

DP 刷题

发表于 更新于 分类于 阅读次数： Valine：

01背包

Task Computing

题目连接

As it says, Time is Money, Efficiency is Life. A client has a computing task waiting for uploading to the cloud servers. However, due to the resource limits and many other tasks, a task usually cannot be worked on a single server but multiple servers, one after another. You, as an employee of a cloud server provider who specializes in task allocation, need to select several servers from a limited number of cloud servers to perform calculations. We know that even the same servers will perform differently in different environments.

There are nn cloud servers available in the vicinity of the client’s region numbered from $1$ to $n$. The ii-th cloud server has two parameters: $w_i$ and $p_i$, which indicate the computing power and transmission efficiency of that server, respectively. The supervisor requires that each task must be computed by exactly $m$ of these servers. The client’s computational task is not parallelizable, so you must sequence the work of the $m$ servers to maximize the total computational efficiency. We define the total computational efficiency as follows:
$\sum_{i=1}^m {w_i} \prod_{j=0}^{i-1} {p_i}$

输入描述

The first line contains two integers $n$,$m$ ($1 \le n \le 10_{5}$ , $1 \le m \le {min(n,20)}$) denoting the number of cloud servers and servers that you have to select.

The second line contains $n$ integers $w_1$,$w_2$,$\ldots$, $w_n$,($1 \le {w_i} \le 10_{9}$), denoting the servers’ computing power.

The third line contains $n$ integers $q_1$,$q_2$,$\ldots$, $q_n$ ($8000 \le q_i \le 12000$)
where $p_i$ =$\frac {q_i}{10000}$ denotes the ii-th server’s transmission efficiency.

输出描述

Output a float number denoting the maximal total computational efficiency. Your answer is considered correct if the relative or absolute error between yours and the standard solution is not greater than $10^{-6}$

样例1

输入

1
2
3
5 2
1 2 3 4 5 
12000 11000 10000 9000 8000

输出

1
8.500000000

思路

1.首先，每个机器选取的先后顺序会影响其价值，先对其进行排序。

设两个机器分别为 $x,y$,

当$x$在前，$y$在后的价值为 : $w_x * p_k + w_y * p_x * p_k$

当$y$在前，$y$在后的价值为 : $w_y * p_k + w_x * p_y * p_k$

令 式1>式2 得 :

$w_x + w_y * p_x > w_y + w_x * p_y$，按照该式子排序

2.排序后，不论从前到后还是从后到前，均为一个有顺序的子序列，所以前后方向不重要。

3.越靠后面选择的，$p$的影响更大。

设三个设备$1,2,3$，则价值为

$w_1 + w_2 * p_1 + w_3 * p_1 * p_2 = p_1 * (w_2 + w_3 * p_2) + w_1$

以此类推
因此从最后选的开始更新，价值越小，排序越靠后，越先更新，即$(n~1)$

4.dp方程 $f[i][k]$ 表示考虑到 第 i 个， 装了 m 个的最大值

转移方程: $f[i][k]=max(f[i][k],f[i+1][k-1] * p[i] + w[i])$

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int INF=0x3f3f3f;
typedef long long ll;
struct node
{
    double w,p;
}no[MAXN];
double f[MAXN][30],P[30][MAXN];
bool cmp(node x,node y)
{
    return (x.w+x.p*y.w)>(y.w+x.w*y.p);
}
int main()
{ 
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>no[i].w;
    for(int i=1;i<=n;i++) cin>>no[i].p,no[i].p/=10000;
    sort(no+1,no+n+1,cmp);
    for(int i=n;i>=1;i--)
    {
        for(int k=1;k<=m;k++)
        {
            f[i][k]=max(f[i][k],no[i].w+f[i+1][k-1]*no[i].p);
        }   
        for(int k=1;k<=m;k++) f[i][k]=max(f[i][k],f[i+1][k]);       
    }
    printf("%lf",f[1][m]);
    return 0;
}

线性DP

P1681 最大正方形-二

题目连接

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e3+10;
int f[MAXN][MAXN][2],a[MAXN][MAXN]; 
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	int ans=1;
	int p=min(n,m);
	int t=1;
	for(int L=2;L<=p;L++)
	{
		t=0;
		for(int i=n-L+1;i>=1;i--)
		{
			for(int j=m-L+1;j>=1;j--)
			{
				if(L==2)
				{
					if((a[i][j]==0&&a[i+1][j+1]==0&&a[i+1][j]==1&&a[i][j+1]==1)||(a[i][j]==1&&a[i+1][j+1]==1&&a[i+1][j]==0&&a[i][j+1]==0))
					{
						f[i][j][L%2]=1;
					}
				}
				else
				f[i][j][L%2]=f[i][j][(L-1)%2]&&f[i+1][j][(L-1)%2]&&f[i][j+1][(L-1)%2]&&f[i+1][j+1][(L-1)%2];
				if(f[i][j][L%2])
				{ans=L;t=1;
				}
				//cout<<L<<" "<<ans<<endl;
			}
		} 
		if(t!=1) L=p+1;
	}
	cout<<ans;
	return 0;
}

数位DP

数字计数问题

题目连接

思路

设计一个 $Count$ 函数，用来统计$ [1,num] $中，$x$ 的个数，

则每一个数码的答案就是 $Count(b,x)- Count(a-1,x)$，类似于前缀和的想法。

其他函数解释

$pow10(x)$ ，用来求 $10^x$。

$get(q,L,R)$, 用来求某个数中，处在$[L,R]$位置上的数值为多少。

Count函数

假设求数字 $abcdefg$ 中 $d$ 位置 $x$ 的个数（先不考虑$0$）

分两种情况：

  1. 前面选取 $[000,abc-1]$（$0$ 则是 $[001,abc-1]$），后面可以随便选取，即$[000,efg]$，总数：$ans+=abc*1000$。

  2. 当前面选取 $abc$，则要继续分类讨论 $d$ 与 $x$ 的大小关系

    1). 当 $d<x$ 时，数字不在范围内，不符合要求

    2). 当 $d=x$ 时，后面可取 $[000,efg]$，即 $ans+=efg+1$

    3). 当 $d>x$ 是，后面可取 $[000,999]$，即 $ans+=1000$

最后，对于每一个数字，循环一下每一个位置，就是的 $Count$ 的值了。

记得开 $long long$ ! ! !

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pow10(int x)
{
	//if(x<0) return 1;
	ll res=1;
	while(x--) 
	{
		res*=10;
	}
	return res;
}
ll get(vector<int> q,int l,int r)
{
	ll res=0;
	for(int i=r;i>=l;i--)
	{
		res=res*10+q[i];
	}
	return res;
}
ll Count(ll p,int x)
{
	if(p==0) return 0;
	vector<int> num;
	while(p)
	{
		int t=p%10;
		num.push_back(t);
		p/=10;
	}
	int n=num.size();
	ll ans=0;
	for(int i=0;i<n;i++)
	{
		if(x==0&&i==n-1) continue;//0不能是第一个数 
		if(x!=0&&(i<n-1)) ans+=pow10(i)*get(num,i+1,n-1);//情况1
		else if(i<n-1) ans+=pow10(i)*(get(num,i+1,n-1)-1);情况1（0）
		if(num[i]>x) ans+=pow10(i);//情况2.3
		else if(num[i]==x) ans+=get(num,0,i-1)+1; //情况2.2
	}
	return ans;
}
int main()
{
	ll a,b;
	cin>>a>>b;
	if(a>b) swap(a,b); 
	for(int i=0;i<=9;i++)
	{
		ll suma=Count(a-1,i);
		ll sumb=Count(b,i);
		cout<<sumb-suma<<" ";
	}
	return 0;
}