2021CCPC華為雲挑戰賽 部分題題解

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\n",x)
#define putl(x) printf("%lld\n",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);
}
//以吾之血,鑄吾最後的亡魂.