企业建站工具,官方网址,佛山app开发公司,wordpress禁止评论前言
全体爆零#xff0c;十分开心 正题 T1#xff1a;矩阵
大意
就是N个矩阵#xff0c;然后进行矩阵乘法(n∗mn∗m和m∗pm∗p的矩阵相乘就会变成n∗pn∗p的矩阵并且运算次数是n∗m∗pn∗m∗p)#xff0c;然后求最小乘法运算次数。
考试时
一直以为会是图论#xff…前言
全体爆零十分开心 正题 T1矩阵
大意
就是N个矩阵然后进行矩阵乘法(n∗mn∗mn*m和m∗pm∗pm*p的矩阵相乘就会变成n∗pn∗pn*p的矩阵并且运算次数是n∗m∗pn∗m∗pn*m*p)然后求最小乘法运算次数。
考试时
一直以为会是图论然后想来想去什么网络流SPFA啊然后就是不会做。
解题思路
首先讲解一下矩阵乘法的性质 假设有两个矩阵A和B A∗B≠B∗AA∗B≠B∗AA*B\neq B*A 由此因为题目说矩阵一点可以进行相乘所以前一个矩阵的宽一定等于后一个矩阵的长然后就可以进行区间dp f[i][j]f[i][j]f[i][j]表示将i∼ji∼ji \sim j合并为一个矩阵的最少运算次数 然后枚举中间分割线midmidmid表示i∼midi∼midi \sim midmid1∼jmid1∼jmid+1 \sim j分开合并然后所有的取最小值。
代码
#includecstdio
#includealgorithm
#includecstring
using namespace std;
int n,a[501],b[501],f[501][501];
int main()
{memset(f,127/3,sizeof(f));scanf(%d,n);for (int i1;in;i){scanf(%d%d,a[i],b[i]);f[i][i]0;//初始化}for (int j2;jn;j){for (int ij-1;i1;i--){for (int midi;midj;mid)f[i][j]min(f[i][j],f[i][mid]f[mid1][j]a[i]*b[mid]*b[j]);//动态转移}}printf(%d,f[1][n]);//输出
} T2圆盘取数
大意
有一个圆盘上面有n个数指针开始时指向第一个数之后可以取走离指针距离不超过k里面的数取走数代价是数的值然后指针移动一格需要消耗代价为当前剩下最大的数。求取走所有数的最小代价。
考试时
开始时题目理解错了然后后来改正后打了个贪心然后WA
解题思路
首先我们可以发现取数字无论何时取走都需要固定的代价代价就是所有数的和所以我们只需要求指针转动的代价就好了。
首先我们先在不移动指针的情况下取走数字 然后将剩余部分展开
然后这就是一条链了然后我们可以顺路收掉所有的所以每次剩下的一点只会是一段区间。 因为现在指针离最左边和最右边刚好都是k移动一格也只能多取一个数所有我们就可以把k的问题去掉了。 之后我们就可以进行区间dp f[i][j][0/1]f[i][j][0/1]f[i][j][0/1]表示只剩下i∼ji∼ji \sim j的区间时指针在左/右边距离k。 然后我们现在重新定义这条链为1∼n1∼n1 \sim nnnn为这条链的长度，然后我们要一个一个的去掉，所以我们是枚举一个w(n#x2212;1#x223C;1)" role="presentation">w(n−1∼1)w(n−1∼1)w(n-1 \sim 1)表示目前的长度然后枚举i表示开头。 之后我们要求f[i][j][0/1]f[i][j][0/1]f[i][j][0/1]了我们有三种方式转移到f[i][j]f[i][j]f[i][j]我们拿在左边来计算一是原本指针就在那个方向的左边那么这样移动一格就好了
f[i−1][j][0]max[i−1][j]f[i−1][j][0]max[i−1][j]
f[i-1][j][0]+max[i-1][j] 然后另一种是左一格的情况转一圈过来取 f[i−1][j][1](n−w)∗max[i−1][j]f[i−1][j][1](n−w)∗max[i−1][j]
f[i-1][j][1]+(n-w)*max[i-1][j] 最后一种是右一格的情况转一圈过来取 f[i][j1][1](n−w1)∗max[i][j1]f[i][j1][1](n−w1)∗max[i][j1]
f[i][j+1][1]+(n-w+1)*max[i][j+1] 动态转移方程 f[i][j][0]minf[i−1][j][0]max[i−1][j],f[i−1][j][1](n−k)∗max[i−1][j],f[i][j1][1](n−k1)∗max[i][j1]f[i][j][0]minf[i−1][j][0]max[i−1][j],f[i−1][j][1](n−k)∗max[i−1][j],f[i][j1][1](n−k1)∗max[i][j1]
f[i][j][0]=min{f[i-1][j][0]+max[i-1][j],f[i-1][j][1]+(n-k)*max[i-1][j],f[i][j+1][1]+(n-k+1)*max[i][j+1]}然后求右边的反过来就好了 代码
#includecstdio
#includealgorithm
#includecstring
#define mins(x,y,z) min(x,min(y,z))
using namespace std;
int n,k,t,answ,ans,a[2010],f[2010][2010][2],m[2010][2010];
int main()
{freopen(data10.in,r,stdin);scanf(%d%d,n,k);nn-2*k-1;for (int i-k;ink;i){scanf(%d,t);answt;//计算取数代价if (i1in) a[i]t;//去掉开始可以取的}for (int i1;in;i){int maxs0;for (int ji;jn;j)m[i][j](maxsmax(maxs,a[j]));//预处理区间最大}ans2147483647/3;for (kn-1;k1;k--){f[0][k][0]f[0][k][1]700000000;f[n-k1][n1][0]f[n-k1][n1][1]700000000;//防止取到界外for (int i1;in-k1;i){int jik-1;f[i][j][0]mins(f[i-1][j][0]m[i-1][j],f[i-1][j][1](n-k)*m[i-1][j],f[i][j1][1](n-k1)*m[i][j1]);//动态转移f[i][j][1]mins(f[i][j1][1]m[i][j1],f[i][j1][0](n-k)*m[i][j1],f[i-1][j][0](n-k1)*m[i-1][j]);//动态转移}}for (int i1;in;i)ansmin(ans,min(f[i][i][0],f[i][i][1])a[i]answ);//求最小代价printf(%d,ans);
} T3扑克游戏
大意
一颗无穷大的完全二叉树 你有n张数值不同的牌如果你将一张牌放到了一个节点那么代价就是num−(dep−1)num−(dep−1)num-(dep-1)并且封锁子树然后要求所有的牌放在树上的最小代价。
考试时
敲了一个贪心每次尽量平均分成两半子树传然后只剩一个数时返回信息最后进行统计
贪心代码
#includecstdio
#includealgorithm
using namespace std;
int tot,n,a[10001],s,v[10001];
int tx(int x,int num,int sum,int dep)
{if (x1dep!0) return sum*dep;int s0,k0;tot;for (int i1;in;i)if (v[i]num){if (s*(dep1)a[i]*(dep1)sum*(dep1)/2) sa[i],v[i]tot,k;else v[i]tot1;}tot;int wtot;return tx(k,w-1,s,dep1)tx(x-k,w,sum-s,dep1);
}
int main()
{ scanf(%d,n);for (int i1;in;i)scanf(%d,a[i]),sa[i];sort(a1,a1n);printf(%d,tx(n,0,s,0));
}
然后全WA
解题思路
就是合并果子复制粘贴 原理 合并果子时最后一堆需要消耗suma[i](i1∼n)suma[i](i1∼n)sum+=a[i](i=1\sim n)然后假设上一堆的需要果子子集S那么代价就是sumx(x⊆S)sumx(x⊆S)sum+=x(x\subseteq S)。那么我们发现该数合并的次数其实就是这道题放在的深度加1。
正确原理是哈夫曼树自己看我也不会。
代码
#includecstdio
#includealgorithm
#includecstring
using namespace std;
int k,x,num,n1,n2,a1[30001],a2[30001],t[20001],w,sum;
int main()
{scanf(%d,num);memset(a1,127/3,sizeof(a1));memset(a2,127/3,sizeof(a2));for (int i1;inum;i){scanf(%d,x);t[x];//桶}for (int i1;i20000;i){while (t[i])//通排序{t[i]--;a1[n1]i;}}int i1,j1;k1;while (knum){if (a1[i]a2[j])//取最小值{wa1[i];i;}else{wa2[j];j;}if (a1[i]a2[j])//取第二次{wa1[i];i;}else{wa2[j];j;}a2[n2]w;//加入第二个队列k;//计算合并次数sumw;//计算价值}printf(%d,sum);
}
合并果子O(n)O(n)O(n)原理详见 https://blog.csdn.net/mr_wuyongcong/article/details/80030964 后续
矩阵乘法白学了合并果子白学了区间dp白学了。这就是第一天的收获233。
