大二下学期第六周周报
2019/4/7 xzc
本周做的题有：
-
周赛：B,C,D,E(A是WF的A题，不想补了)
C题蘑菇园 -
基础DP1三道水题：
B.Ignatius and the Princess IV map水题
I.最少拦截系统 (LIS的运用)
M.Harry And Dig Machine 暴力DFS(twt用我HDU的号交了一发状压dp) -
2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛)
D题：简单鸽巢原理+组合数
(篇幅有点儿少，贴个代码吧)
/*
xzc201804040921157 提交的代码
提交时间：2019-04-06 14:08:25 语言：C++ 代码长度：993 运行时间： 48 ms 占用内存：31712K
运行状态：答案正确
*/
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 2e6+100;
const int mod = 1e9+7;
LL r[maxn];
LL fac[maxn];
LL fast_pow(LL a,LL b)
{
LL ans = 1;
while(b)
{
if(b&1) ans = ans*a%mod;
a = a*a%mod;
b>>=1;
}
return ans;
}
void init()
{
fac[0] = 1;
r[0] = 1;
For(i,1,2000000) fac[i] = fac[i-1]*i%mod;
r[2000000] = fast_pow(fac[2000000],mod-2);
Rep(i,1999999,1)
r[i] = r[i+1]*(i+1)%mod;
}
LL C(int n,int m)
{
if(n<m||m<0) return 0;
return fac[n]*r[m]%mod*r[n-m]%mod;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int m,n;
init();
while(cin>>n>>m)
{
LL ans1 = C(m-1,n-1); //C(m-1,n-1)
LL ans2 = C(n+m-1,n-1); //C(m-1,n+m-1)
printf("%lld %lld
",ans1,ans2);
}
return 0;
}
还进行了经典(简单)dp的复习(扫盲)
经典dp问题
- 最长上升子序列： nlogn lower_bound dp[i]记录的是长度为i的子序列的末尾的最小值
/*
I-最少拦截系统
Status: Accepted Memory: 1444kB
Length: 1240 Lang: G++
Submitted: 2019-04-04 13:07:41
*/
#include <bits/stdc++.h>
#define Mst(a,b) memset(a,(b),sizeof(a))
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 1e6 + 100;
int a[maxn];
int dp[maxn];
int pos[maxn];
/*
这道题求最长非递减子序列的个数，有LIS性质：答案等于最长递增子序列的长度(LIS记录的是每个递减序列的结尾)
可以在更新dp数组的同时顺便记录导弹拦截的方案
pos[]记录a[i]在递推过程中在dp[]中的下标，便于还原路径(但这道题vector记录方案就已经知道LIS了)
*/
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
while(scanf("%d",&n)!=EOF)
{
For(i,1,n) scanf("%d",a+i);
vector<int> v[n+1];
dp[1] = a[1];
pos[1] = 1;
int len = 1;
v[1].push_back(a[1]);
For(i,2,n)
{
if(a[i]>dp[len])
{
dp[++len] = a[i];
pos[i] = len;
v[len].push_back(a[i]);// record the path
}
else
{
int m = lower_bound(dp+1,dp+len+1,a[i])-dp;
dp[m] = a[i];
v[m].push_back(a[i]); //record the path
}
}
printf("%d
",len);
//print the path
/*
For(i,1,len)
{
cout<<i<<": ";
for(auto &t:v[i]) cout<<t<<" ";cout<<endl;
}
*/
}
return 0;
}
- 最大子段和 ： O(n)
//a[0] = 0
for i in range (1,n):
dp[i] = a[i] + max(0,dp[i-1)
ans = max(ans,dp[i])
- 最大循环子段和： 最大的 和sum-最小的取max
- 最大公共子序列： dp O(n*m)
dp[i][j] = max(dp[i-1][j],dp[i)[j-1],dp[i-1][j-1]+a[i]==b[j])
//应该是这样的吧,dp[i][j]代表a的前i位的和b的前j为最长公共子序列的长度
- 最大公共子串 ： 后缀数组(nlogn)
去学一下？ - 最大子矩阵和 ： O(n^3) 51Nod 1051
预处理竖的前缀和，枚举up,down，宽度用最大子段和
//author: xzc
#include <bits/stdc++.h>
#define Mst(a,b) memset(a,(b),sizeof(a))
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 510;
LL a[maxn][maxn];
LL s[maxn][maxn],res,ans;
int main()
{
int m,n;
while(scanf("%d%d",&n,&m)!=EOF)
{
For(i,0,500) s[0][i] = s[i][0] = 0;
For(i,1,m)
For(j,1,n)
scanf("%lld",&a[i][j]),
s[i][j] = a[i][j]+s[i-1][j];
res = a[1][1];
For(up,1,m)
{
For(down,up,m)
{
ans = 0;
For(k,1,n)
{
ans = max(ans,0ll)+s[down][k]-s[up-1][k];
res = max(res,ans);
}
}
}
printf("%lld
",res);
}
return 0;
}