JZOJ 2017.8.6 B组总结

第一题

题目大意：求一个有重量限制的天平最多可以放重量多少的砝码 题目链接：https://jzoj.net/senior/#main/show/1252

思路：DFS+剪枝+前缀和 先记录一波**前缀和**s[i] 那么我们倒过来搜，搜到第i个，如果前面的全取了都不超过限制，那么直接加上，退出（可以用前缀和实现） 否则枚举i~1，看能否不超限制，不超就放

代码：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m; long long ans=-1,sum[1010],a[1010]; void dfs(int c,long long count) { if(count>m) return; if(sum[c-1]+count<=m) { ans=max(ans,sum[c-1]+count); return; } ans=max(ans,count); for(int i=1;i<c;i++) { count+=a[i]; dfs(i,count); count-=a[i]; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } dfs(n+1,0); printf("%lld\n",ans); return 0; }

第二题

题目大意：有m-1次坐车的机会，要使最后到n市，从一个市出发到其他市的马车都有一个周期，周期不同费用不一样。现在要求满足情况的最小费用 题目链接：https://jzoj.net/senior/#main/show/1274

思路：dp 设f[i][j]为第i天到达j市的最小费用 然后强行转移，f[i][j]=min（f[i][j],f[i-1][k]+v[j][k][(i-1)%t[j][k]+1]）转移式类似于Floyd 时间复杂度O(N^2M)

第三题

题目大意：如果矩阵的每一个点的权值表示从(0,0)开始到这个点的方案数，求出从(0,0)出发到(n,m)的最小权值数 题目链接：https://jzoj.net/senior/#main/show/3777

思路：组合数+快速幂 保证n>m,其实这个矩阵的最小权值的路线就是（0,0）~（1,n）~（m,n） 那么答案就是n+1+f[m][1~n] 知道f[i][j]=C(j,j+i),C(m-1,n-1)+C(m,n) 答案就转移为C(n-m+1,m)+n 在求组合数时因为要取模，所以只能用逆元的想法，打快速幂

代码：

#include<cstdio> #include<iostream> using namespace std; const long long mo=1000000007; long long ans,n,m,t; long long ksm(long long base,long long exp) { long long r=1; while (exp) { if (exp&1) r=(r*base)% mo; base=(base*base)%mo; exp>>=1; } return r; } long long c(long long x,long long y) { long long mx=1; for (long long i=x;i>x-y;--i) mx=(mx*i)% mo; for (long long i=m;i>0;--i) mx=(mx*ksm(i,mo-2))%mo; return mx; } int main() { scanf("%lld%lld",&n,&m); if (n<m) {t=n;n=m;m=t;} printf("%lld",(c(n+m+1,m)+n)% mo); }