1 条题解

  • 0
    @ 2023-1-2 21:20:17

    解题思路

    状态

    这是一道典型的区间 DP。自然的,状态可以顺理成章地设计为 f(i,j)f(i,j),表示前 ii 个人抄前 jj 本书所需要的时间。f(1,j)f(1,j) 初始化为 k=1jak\sum^{j}_{k=1}a_k,其中 aa 是输入的数组。

    转移

    第一阶段是人的个数,那么,第一层循环就枚举人的个数;

    第二阶段,枚举书。假设从 iijj 本书交给下一个人抄,那么当前时间是 max{fpeo1,i,bjbi}\max \{f_{peo-1,i}, b_j-b_i\}bbaa 的前缀和数组。这个转移的意思就是,如果给新的一个人抄写,所需时间为原来时间和此人花费时间的较大值。

    路径

    此为本题的难处。考虑贪心,为了让前面的人少抄,后面的人要多抄。同时,为了让每个人都有活儿干,循环时需要特判。

    奉上代码

    // Copying Books
    #include <iostream>
    #include <cstring>
    #include <vector>
    #define int long long
    #define SIZE 505
    #define all(x) x.begin(), x.end()
    #define debug(x) cout<<#x<<":"<<x<<endl;
    using namespace std;
    
    int n, k;
    int f[SIZE][SIZE];
    int a[SIZE]={0}, b[SIZE]={0};
    
    vector<int> fk;
    
    void printAll(int x, int i, int cnt)
    {
    	if(i==0) return;
    	int sum=0;
    	int j;
    	for(j=i; j>k-cnt-1 && sum+a[j]<=x; j--)
    		sum+=a[j];
    	printAll(x, j, cnt+1);
    	fk.push_back(i);
    }
    
    signed main()
    {
    	int T; cin>>T;
    	while(T--)
    	{
    		cin>>n>>k;
    		memset(f, 0x3f, sizeof(f));
    		for(int i=1; i<=n; i++)
    			cin>>a[i], b[i]=b[i-1]+a[i], f[1][i]=b[i];
    		for(int peo=2; peo<=k; peo++)
    			for(int i=1; i<n; i++)
    				for(int j=i+1; j<=n; j++)
    					f[peo][j]=min(f[peo][j], max(f[peo-1][i], b[j]-b[i]));
    		fk.clear();
    		printAll(f[k][n], n, 0);
    		int k=0;
    		for(int i=1; i<=n; i++)
    		{
    			if(i!=n)
    				cout<<a[i]<<" ";
    			else
    				cout<<a[i];
    			if(i==fk[k] && i!=n)
    			{
    				k++; cout<<"/ ";
    			}
    		}
    		cout<<endl;
    	}		
    
    	return 0;
    }
    
    • 1

    信息

    ID
    510
    时间
    3000ms
    内存
    10MiB
    难度
    10
    标签
    (无)
    递交数
    1
    已通过
    1
    上传者