https://ac.nowcoder.com/acm/contest/64593

  • A题签到
  • B题值得说得是对非降序的理解：非降序表示数组中的前一个数要<=下一个数
  • C题也算dp，因为需要注意遍历顺序，计算的是所有子串的的权重，我们知道枚举所有子串需要O(n2)O(n^2)的复杂度，按照本题数据范围显然不能O(n3)O(n^3)，我们只能在枚举过程中去维护计算每个字串的权重。
    本题的特点是一个str的起点一旦确定，它变换的最终形态也就确定。所以我们考虑枚举起点，再枚举终点，对于每个起点终点确定的子串我们考虑假设起点是0的话我们需要变换c0次，起点是1的话我们需要操作c1次，两者取最小值就是当前子串的权重。

那怎么快速求出每个子串需要变换次数呢？

以下操作都是在起点确定的情况下进行，一旦起点迭代，我们需要重新维护c0，c1。

  • 这就需要dp的思想了，我们需要从上一个状态转移过来，上一个状态也就是起点相同，长度比当前短1的子串，这样来看我们只需要处理新出现这个字符即可，根据这个字符是0还是1以及与起点的距离来维护c0，c1。我们可以看到在起点固定的一轮循环中，c0，c1是不断变化的，所以我们要及时累加答案。
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
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];

void solve(){
	string s;
	cin>>s;
	int len=s.length();
	int ans=0;

	for(int i=0;i<len;i++){
			int c1=0,c0=0;
		for(int j=i;j<len;j++){
			int tmp=s[j];
			if(tmp=='0'&&(j-i)%2==0||tmp=='1'&&(j-i)%2==1)c1++;
			else c0++;
			ans+=min(c1,c0);
		}
	
	}
	cout<<ans<<endl;
	}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
   t=1;

    while (t--) {
solve();
    }
    return 0;
}
  • D题是线性dp,如果看不出来，说明对线性dp理解不够。本题需要反着考虑，不考虑删哪些数，而考虑是从n个数中选m个数，使得这m个数两两是倍数关系，对于这个问题我们如果能想到转化为成子问题就能想到动态规划。

对于dp我们需要考虑枚举顺序，保证子问题的的状态已经被计算过，题中我们考虑整除，所以对数组进行排序，由小到大枚举。f[i][k]表示从前i个数中选k个数且选出来的最大数是啊a[i],题面描述中说了不会存在两个相同的数，这也保证了这种dp数组的可行性。

我们枚举1-i中能够被整除i的数j，对于每一个j我们都可以转移状态f[i][k]=(f[i][k]+f[j][k-1])，也就是从前j个数中选k-1个数，不断累加答案。最终答案是枚举每个数是最大数时从他前面选m-1个数的方案数总和

对于时间复杂度：在前面n2n^2次枚举中最多会有log⁡2(n2)\log_2 (n^2)次会执行if里的循环，循环内部是n次，这部分不是算法瓶颈，最终复杂度是 O(n2)O(n^2) ，不会TLE。

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
58
59
60
61
62
63
// Problem: 小美的元素删除
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/64593/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 1e3+2;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-8;
int n, m;
int a[N];
int f[N][N];

void solve(){
	cin>>n>>m;
	m=n-m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i][1]=1;
	}
	sort(a+1,a+n+1);
	int res=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i]%a[j]==0){
				for(int k=2;k<=m;k++){
					f[i][k]=(f[i][k]+f[j][k-1])%mod;
				}
			}
		}
		res+=f[i][m];
		res%=mod;
	}
	cout<<res<<endl;
}
signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
  t=1;

    while (t--) {
solve();
    }
    return 0;
}