C. Two Arrays (dp、思维)

浅浅的花香味﹌ 2021-07-16 19:19 447阅读 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 条评论，447人围观）

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

相关阅读

相关 leetcode Median of Two Sorted Arrays

题目： There are two sorted arrays nums1 and nums2 of size m and n respectively. Find th

ゞ浴缸里的玫瑰/ 2022年08月05日 00:59/ 0 赞/ 161 阅读

相关 [leetcode]: 349. Intersection of Two Arrays

1.题目描述 Given two arrays, write a function to compute their intersection. Example:

梦里梦外;/ 2022年06月15日 21:29/ 0 赞/ 142 阅读

相关 [leetcode] Median of Two Sorted Arrays

\[4\] Median of Two Sorted Arrays There are two sorted arrays nums1 and nums2 of size

Dear 丶/ 2022年06月15日 12:37/ 0 赞/ 199 阅读

相关 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 赞/ 163 阅读

相关 6. Merge Two Sorted Arrays

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

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

相关 349. Intersection of Two Arrays

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

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

相关 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 赞/ 147 阅读

相关 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 赞/ 149 阅读

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

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

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

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

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

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