你最愿意做的哪件事，才是你的天赋所在

0%

发表于 Valine：

题目链接

方格取数

思路

用思维DP，dp[i][j][k][l]表示第一个点走到i,j,第二个点走到k,l的最大值。
然后根据转移，第一个点可以由左或者上转移，第二个点也是。那么一共有四种组合。
左左，上上，左上，上左。然后根据这两点的坐标是否相同，决定贡献。

代码实现

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll dp[11][11][11][11];
int mp[11][11];
int n; 
int main()
{
	scanf("%d",&n);
		int x,y,v;
		while(cin>>x>>y>>v)
        {
            if(x==0&&y==0&&v==0)break;
            mp[x][y]=v;
        }
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	for(int k=1;k<=n;k++)
	for(int l=1;l<=n;l++)
	{
        dp[i][j][k][l]=max(dp[i-1][j][k-1][l],dp[i][j][k][l]);//左左 
        dp[i][j][k][l]=max(dp[i][j-1][k][l-1],dp[i][j][k][l]);//上上
		dp[i][j][k][l]=max(dp[i-1][j][k][l-1],dp[i][j][k][l]);//左上
		dp[i][j][k][l]=max(dp[i][j-1][k-1][l],dp[i][j][k][l]);//上左
		if(i==k&&j==l)dp[i][j][k][l]+=mp[i][j];
		else dp[i][j][k][l]+=(mp[i][j]+mp[k][l]); 
	}
	cout<<dp[n][n][n][n]<<endl;
}

发表于 Valine：

题目链接

Bomb

思路

这是一道数位DP的模板题目，可以转化成不要49，是反正写的。
具体参考我前面的不要62这篇博客。正着写也有方法。
首先DP分为两种情况。
1.先搜到49，那么后面就不用搜了，直接加上后面的答案。
2.没搜到49，继续往下搜，并且带入一个状态前一个是否是否为4.

代码实现

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
#include<bits/stdc++.h>
using namespace std; 
#define ll long long 
ll dp[50][2];
int a[50];
ll z[50]={1};
ll x,y;
ll dfs(int pos,bool is4,bool limit)
{
	if(pos==-1)return 0;
	if(!limit&&dp[pos][is4]!=-1)return dp[pos][is4];
	int up = limit?a[pos]:9;
	ll temp = 0;
	for(int i=0;i<=up;i++)
	{
		if(i==9&&is4)
		{
			temp+=limit?x%z[pos]+1:z[pos];
		}
		else temp+=dfs(pos-1,i==4,limit&&i==a[pos]);
	}
	return limit?temp:dp[pos][is4]=temp;
}
ll solve()
{
	int pos = 0;
	while(y)
	{
		a[pos++]=y%10;
		y/=10;
	}
	return dfs(pos-1,false,true);
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<50;i++)
	z[i]=z[i-1]*10;
	memset(dp,-1,sizeof(dp)); 
	while(n--)
	{
		cin>>x;
		y=x;
		printf("%lld\n",solve());
	}
}
### 总结
做完这道题，才能算简单理解数位DP的思想吧。
同一种算法，做的题越多，理解越深刻，思维能够发散的程度越广。

发表于 Valine：

Work-Scheduling

题目链接

Work-Scheduling

思路

时间从前往后贪心，创建一个堆，堆的大小就是当前选择的最远时刻，所以每此比较t和堆的大小。
1.t>q.size()时，直接入堆
2.t<q.size()时, 时间已经过了，这份工作无效了
3.t==q.size()时，判断当前工作是否值得，值得的话，进堆，然后把贡献最小的出堆。

阅读全文 »

发表于 更新于 Valine：

题目链接

D. Beautiful numbers

思路

很明显用数位DP来写，那么怎么维护状态呢？一个数能够整除任一位数我们转化成这个数可以整除他们的最小公倍数。
那么包含1~9的最小公倍数是2520.当我们到最后一个数字的时候判断余数是否能够整除当前的lcm就可以了。但是有一个问题。
如果按照上述的思路，我们需要维护一个三维DP数组，也就是dp[50][2520][2520]，第一位表示位置，第二位表示当前的公倍数，第三位表示当前的余数，那么这个数组肯定超内存了。
所以我们考虑离散化，实际上他的公倍数只有48个，就是1-9的任意组合，那么我们把中间位置的离散成50大小的就可以写了。

阅读全文 »

发表于 Valine：

题目链接

Governing sand

思路

这道题用线段树的数据结构来优化，总体思想就是枚举最高的树，然后统计当前的答案。
但是统计答案的时候我们的cost值：
设当前高度为h，那么需要把全部大于h的树砍掉，以及小于h的树需要剩下num[h]-1。
前半部分的消费我们可以用前缀和来维护，因为我们从高枚举到低。
而后半部分我们则用线段树来维护。
线段树维护：
每个节点维护两个值，花费以及数量。
每次查询即可查询到砍到剩下num[h]-1需要的花费，加上前缀和，就是我们需要的答案了。
这题如果不用快读可能会T，如果T了试试快读

阅读全文 »

发表于 更新于 Valine：

题目链接

Codeforces Round #578 (Div. 2)

A

思路

500分的题目，直接暴力模拟

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n,ans[10];
string s;
int main(void){
	cin>>n>>s;
	for(int i=0;i<n;i++){
		if(s[i]=='L'){
			for(int j=0;j<10;j++)if(ans[j]==0){ans[j]=1;break;}
		}
		else if(s[i]=='R'){
			for(int j=9;j>=0;j--)if(ans[j]==0){ans[j]=1;break;}
		}
		else {
			ans[s[i]-'0']=0;
		}
	}
	for(int i=0;i<10;i++)cout<<ans[i];
	return 0;
}
阅读全文 »

发表于 Valine：

题目链接

HDU 2089

思路

数位DP，我的理解就是求一个区间内满足一些条件的数的个数。
通过记忆化搜索和动态规划的方法让我们能够更快速的得到答案。

代码模板

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[20];
int dp[20][2];
int dfs(int pos,int pre,int sta,bool limit)
//pos是当前枚举的位置，pre是针对这道题的前面是否出现6，然后sta指的是当前的状态
//for循环内放入限制条件
{
	if(pos==-1)return 1;
	if(!limit&&dp[pos][sta]!=-1)return dp[pos][sta];
	int up = limit?a[pos]:9;
	int tmp = 0;
	for(int i=0;i<=up;i++)
	{
		if(pre==6&&i==2)continue;
		if(i==4)continue;
		tmp += dfs(pos-1,i,i==6,limit&&i==a[pos]);
	}
	if(!limit)dp[pos][sta]=tmp;
	return tmp;
}
int solve(int x)
{
	int pos = 0;
	while(x)
	{
		a[pos++]=x%10;
		x/=10;
	}
	return dfs(pos-1,-1,0,true);
}
int main()
{
	int n,m;
	while(~scanf("%d %d",&n,&m)&&(n||m))
	{
		memset(dp,-1,sizeof(dp));
		printf("%d\n",solve(m)-solve(n-1));
	}
	return 0;
}

发表于 更新于 Valine：

题目链接

2019牛客暑期多校训练营(第八场)

A

题目描述

给出一个大小为N*M的01矩阵，求出包含多少个由1组成的矩形，矩形唯一：即一个矩形不能被另一个矩形包含。

思路

用单调栈处理，栈中储存两个值，一个为该点能够向上延申的最大长度，一个是能够延申到最左边的位置。
向上延申的最大长度很明显能够使用前缀和来解决。
细节处理：
处理好前缀和后，从左上角遍历到右下角，当前位置能够向上延申的最大长度大于当前栈顶元素的最大长度时，就可以进栈。
然后，当栈顶元素能够向上延申的最大长度大于当前位置能够向上延申的最大长度时，这时候判断栈顶元素向左延申的位置是否小于等于下一行中右边0的位置
也就是防止出现
111
111
而计算了两行为两个矩阵的情况。

阅读全文 »

发表于 更新于 Valine：

题目链接

Educational Codeforces Round 70 (Rated for Div. 2)

A

题解

找到第二个字符串的最后一个1，让他能够与第一个字符串1能够相加即可

代码实现

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
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		string s,s1;
		cin>>s>>s1;
		if(s1[s1.size()-1]=='1'&&s[s.size()-1]=='1')
		{
			printf("0\n");
			continue;
		}
	    int pos1; 
		for(int i=0;i<s1.size();i++)
		{
			if(s1[i]=='1')pos1=s1.size()-i;
		}
		for(int i=s.size()-pos1;i>=0;i--)
		{
			if(s[i]=='1')
			{
				printf("%d\n",s.size()-pos1-i);
				break;
			}
		}
	}
}
阅读全文 »