C. Two Arrays (dp、思维)

浅浅的花香味﹌ 2021-07-16 19:19 470阅读 0赞

[题目][Link 1]

a\[i\]\[j\] 表示前i个数字中第i个数字为j的所有情况的非递减序列的数目  
b\[i\]\[j\] 表示前i个数字中第i个数字为j的所有情况的非递增序列的数目

对于非递减数列aa，和非递增数列bb，只要第一个元素满足aa\[1\]>=bb\[1\]整个数列就满足aa中个元素>=bb中对应元素了。那么只需枚举a中第一个元素所有可能与之相对应满足条件的b中第一个元素即可。

另：递增序列第一个数字为j的所有情况=递减序列最后一个数字为j的所有情况 ，递减序列同理

Code

#include<iostream>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    ll a[15][Max], b[15][Max];
    const int Mod = 1e9 + 7;
    
    int main()
    { 
    	int n, m;cin >> n >> m;
    	for (int i = 1;i <= n;i++)a[1][i] = 1, b[1][i] = 1;
    	for (int i = 2;i <= m;i++)
    	{ 
    		for (int j = 1;j <= n;j++)
    		{ 
    			for (int k = 1;k <= j;k++)
    			{ 
    				a[i][j] += a[i - 1][k];
    				a[i][j] %= Mod;
    			}
    		}
    		for (int j = 1;j <= n;j++)
    		{ 
    			for (int k = j;k <= n;k++)
    			{ 
    				b[i][j] += b[i - 1][k];
    				b[i][j] %= Mod;
    			}
    		}
    	}
    	ll ans = 0;
    	for (int i = 1;i <= n;i++)
    	{ 
    		for (int j = 1;j <= i;j++)
    		{ 
    			ans += b[m][i] * a[m][j];
    			ans %= Mod;
    		}
    	}
    	cout << ans << endl;
    }

[Link 1]: https://codeforc.es/contest/1288/problem/C

发表评论取消回复

表情：

评论列表（有 0 条评论，470人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode刷题（C++）——Median of Two Sorted Arrays（Hard）

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the medi

缺乏、安全感/ 2022年06月16日 01:08/ 0 赞/ 122 阅读

相关 Median of Two Sorted Arrays

题目 There are two sorted arrays nums1 andnums2 of size m and n respectively. Find the

深藏阁楼爱情的钟/ 2022年06月07日 00:56/ 0 赞/ 182 阅读

相关 6. Merge Two Sorted Arrays

6. Merge Two Sorted Arrays Description Merge two given sorted integer array A

小灰灰/ 2022年05月27日 07:30/ 0 赞/ 170 阅读

相关【JavaScript】 freecodecamp----Diff Two Arrays

比较两个数组，然后返回一个新数组，该数组的元素为两个给定数组中所有独有的数组元素。换言之，返回两个数组的差异。 function diff(arr1, arr2) {

- 日理万妓/ 2022年05月14日 00:16/ 0 赞/ 82 阅读

相关 349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection. Example 1: Input

刺骨的言语ヽ痛彻心扉/ 2022年04月25日 03:22/ 0 赞/ 117 阅读

相关 Beauty of Array————思维(或者DP)

Beauty of Array Time Limit: 2 Seconds Memory Limit: 65536 KB Edward has an array A

心已赠人/ 2022年04月23日 21:18/ 0 赞/ 158 阅读

相关 Codeforces 1188C Array Beauty dp(看题解）

[Array Beauty][] 最关键的一点是，可以枚举最小值，对于每个最小值算出大于等于它的方案数，这个复杂度是科学的因为 i \ (k - 1) <= dif

超、凢脫俗/ 2021年12月17日 00:21/ 0 赞/ 144 阅读

相关 hdu 5791 (DP) Two

[hdu 5791][] Two Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K

小鱼儿/ 2021年11月10日 08:44/ 0 赞/ 160 阅读

相关 1474 - C. Array Destruction (set、思维)

[题目][Link 1] 思路：可以知道一开始所选的两个数一定要包含最大的一个，假如不包含，那么后面的任何一个数加上最大的那个不可能构成另一个数，按着这个思路走下去，后面

深碍√TFBOYSˉ_/ 2021年07月17日 01:37/ 0 赞/ 336 阅读

相关 C. Two Arrays (dp、思维)

[题目][Link 1] a\[i\]\[j\] 表示前i个数字中第i个数字为j的所有情况的非递减序列的数目 b\[i\]\[j\] 表示前i个数字中第i个数字为j

浅浅的花香味﹌/ 2021年07月16日 19:19/ 0 赞/ 471 阅读