太原网站优化排名,企业信息系统网官网,网站漂浮广告,wordpress 内容调用前言
考试时题目都没看懂#xff0c;题目十分玄学 举个栗子 Sum(sj,s(j1))Sum(sj,s(j1))就是Sum(msj,ms(j1))Sum(msj,ms(j1))and 用1∼n1∼n的数概况1∼10000001∼1000000的数
反正就是十分的玄学 正题 大意
在nn个数m role=presentation style=题目十分玄学 举个栗子 Sum(sj,s(j1))Sum(sj,s(j1))Sum(s_j, s_{(j+1)})就是Sum(msj,ms(j1))Sum(msj,ms(j1))Sum(m_{s_j}, m_{s_{(j+1)}}) and 用1∼n1∼n1\sim n的数概况1∼10000001∼10000001\sim 1000000的数
反正就是十分的玄学 正题 大意
在nnn个数m" role="presentation" style="position: relative;">mmm里选kkk个数。
如果我们选择k" role="presentation" style="position: relative;">kkk个数那么就有一个序列ss1,s2...skss1,s2...sks=s_1,s_2...s_k表示选择第sisis_i个。 然后对于每一个没有被选择的数都会对结果造成一点误差。 如果没有被选择的数编号为iii，对于每一个i" role="presentation" style="position: relative;">iii 如果 is1is1i, 误差是:2∗|Mi−Ms1|2∗|Mi−Ms1|2 * | M_i - M_{s_1} | 如果sjisj1sjisj1s_j,误差是:|2∗Mi−msj−msj1||2∗Mi−msj−msj1|| 2 * M_i - m_{s_j}- m_{s_{j+1}}| 如果iskiski>s_k,误差为:2∗|Mi−Msk|2∗|Mi−Msk|2 * | M_i - M_{s_k} | 求选择最少的数使误差小于eee解题思路先预处理一个g[i][j]" role="presentation" style="position: relative;">g[i][j]g[i][j]g[i][j]表示在i∼ji∼ji\sim j这个区间内选择一个数的最小误差。 然后用一个f[i][j]f[i][j]f[i][j]表示选择第iii个数，前面的已经取了j" role="presentation" style="position: relative;">jjj个数时的情况。 然后每次枚举一个在iii前面的k" role="presentation" style="position: relative;">kkk从f[i][j]f[i][j]f[i][j]转移到f[k][j1]f[k][j1]f[k][j+1]动态转移方程
f[k][j1]max{f[i][j]g[i1][k−1]}f[k][j1]max{f[i][j]g[i1][k−1]}
f[k][j+1]=max\{f[i][j]+g[i+1][k-1]\}代码
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
long long n,e,m[105],g[105][105],f[105][105];
int main()
{memset(f,127/3,sizeof(f));scanf(%lld%lld,n,e);for (ll i1;in;i)scanf(%lld,m[i]);for (ll i0;in1;i)for (ll ji1;jn1;j)for (ll ki1;kj-1;k)if (!i) g[i1][j-1]2*abs(m[k]-m[j]);//特判——左else if (jn1) g[i1][j-1]2*abs(m[k]-m[i]);//特判——右else g[i1][j-1]abs(2*m[k]-m[i]-m[j]);//预处理f[0][0]0;for (ll i0;in;i)for (ll j0;jn;j)if (f[i][j]e)for (ll ki1;kn1;k)f[k][j1]min(f[k][j1],f[i][j]g[i1][k-1]);//动态转移for (ll i2;in1;i)if (f[n1][i]e)//枚举答案{printf(%lld %lld,i-1,f[n1][i]);return 0;}
}
