CDN流量调度问题
题看了没多久就看出来是(DP)的题，然后就设了状态(f[i][j])表示到前(i)个点时已经用了(j)个节点的最小总代价,结果发现转移时(O(nm^2))，但这样只会T掉的，于是就顺利应当的进入了DP优化的思维，奈何无论用上什么伎俩都好像有点不太奏效，以下给出暴力的代码：
rep(i,1,n) rep(j,0,m)
rep(k,1,min(j+1,t[i]))//枚举i的节点数量。
f[i][j]=min(f[i][j],f[i-1][j+1-k]+a[i]/k+(a[i]%k?1:0));
发现难点就在于转移时，(a[i]/k)（向上取整）这个没法很好的处理....之后看来看题解，发现果然是在这里做文章的，这里考虑我们暴力的做法k的范围从1到min(j+1,t[i]),相当于将所有可能的都枚举了。但再仔细的瞅一眼上面这个式子，(a[i]/k=t)（这里向上取整）。也就是说(a[i]=k*t)那(k)和(t)不就是(a[i])的因子吗？不不不...这里由于是向上取整的缘故，所以不是严格意义下的因子，因为我们可以发现对于任意一个数，它都能除以其他数在向下取整的情况下。那我们怎么办呢？考虑到是向上取整的缘故，所以一定有(k*t>=a[i])，并且要求(k)和(a[i])一定时，(t)最小,这样的话，我们也可以通过枚举所谓“因子”的方法枚举(k),若因为k和t是成对存在的我们枚举小的那个，这样的话，我们枚举的范围就是(sqrt{a[i]})。
怎么说呢，这个题反正到最后还是有点不很理解的...
为什么这个k得枚举范围就降了一个(sqrt{a[i]})，大概可以这么说吧，就是你通过分析这个(a[i]/k)向上取整这个得值最多是2*(sqrt{a[i]})，所以有很多的k，(a[i]/k)向上取整对应的值都一样的，这样的情况下，你就根本没必要去枚举那些多余的k值，你只需要知道(a[i]/k)有多少个值，并且他们所对应的最小的k就行了，大的k但和他们贡献相同的就不用枚举了....通过预处理，可以提前缩短我们遍历的状态空间，可以说这个题给我带来的启示很大！
//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define ls p<<1
#define db double
#define rs p<<1|1
#define P 1000000007
#define RE register
#define ll long long
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define ull unsigned long long
#define put(x) printf("%d
",x)
#define putl(x) printf("%lld
",x)
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
#define go(x) for(RE int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=105,M=10050;
int T,n,m,a[N],t[N],f[N][M],size[N];//f[i][j]表示前i个线路用了j的节点的最小代价。
PII v[N][M];//预处理出每个线路的所有不同的向上取整的结果已及所需的节点数。
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
int main()
{
//freopen("1.in","r",stdin);
get(T);
while(T--)
{
get(n);get(m);
rep(i,1,n) get(a[i]);
rep(i,1,n) get(t[i]);
memset(f,0x3f,sizeof(f));
memset(size,0,sizeof(size));
f[0][0]=0;
rep(i,1,n)
{
int temp=0;
rep(j,1,t[i])
{
if(a[i]/j+(a[i]%j?1:0)!=temp)
{
temp=a[i]/j+(a[i]%j?1:0);
v[i][++size[i]]={temp,j};
}
}
}
rep(i,1,n) rep(j,0,m)
{
if(j) f[i][j]=min(f[i][j],f[i][j-1]);
rep(l,1,size[i])
{
if(v[i][l].second-1>j) break;
f[i][j]=min(f[i][j],f[i-1][j+1-v[i][l].second]+v[i][l].first);
}
}
put(f[n][m]);
}
return (0^_^0);
}
//以吾之血,铸吾最后的亡魂.