题目传送门

解题思路:

一道DP,完全背包,不过有点不同于模板.因为本题的每件物品可自由在不同的时间买卖,且不同时间价格不同.

这道题的关键在于要明白一个非常傻逼的性质,就是我在某天买了第i个物品,然后又把它卖出去,其实我啥也没干.

所以,我想将一个物品在第i天买,在第i+n天卖出去,其实可以转化为在第i天买,第i+1,i+2......i+n-1天都当天卖出去然后当天再买回来,第i+n天卖出去.

最后,套完全背包即可.

AC代码:

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 long long t,n,m,a[][],f[],ans;

 int main() {

     scanf("%lld%lld%lld",&t,&n,&m);

     for(int i = ;i <= t; i++)

         for(int j = ;j <= n; j++)

             scanf("%lld",&a[i][j]);

     for(int i = ;i <= t; i++){

         memset(f,,sizeof(f));

         for(int j = ;j <= n; j++)

             for(int x = a[i][j];x <= m; x++)

                 f[x] = max(f[x],f[x-a[i][j]] + a[i+][j] - a[i][j]);

         m = max(m,f[m] + m);

     }

     printf("%lld",m);

     return ;

 }

//CSP-J 2019 T3

巴特西

洛谷 P5662 纪念品

题目传送门

解题思路:

AC代码:

最新文章

热门文章