5-15

ゝ一纸荒年。 2021-11-19 11:31 326阅读 0赞

**[CodeForces - 864E][][Fire][]**

题目大意：一个人的房子着火了，里面有n件物品，第i件物品的价值是pi，抢救它需要ti时间，而在di时间这件物品会被烧完，无法抢救，问救出的最大价值是多少，并输出任意的救援方案。

跟暑假留校选拔的一题类似，就是01背包保存路径，那我们直接可以把dp弄成个结构体，记录权值，以及vector保存相应的物品。

具体思路就是，价值已知，而时间可以看做体积，最大体积无非就是最大的d，2000。不过多了个p和d的限制，我们每个物品可以更新的区域就在\[t,d-1\]之间，在01背包更新时，我们是由前面的最优来决定现在的最优，如果前面都不是最优的那么当前肯定并不是最优。比如当前时间是j选择救第i件物品，得到的最大价值就是dp\[j\]=max(dp\[j\],dp\[j-t\[i\]\]+p\[i\]）,而如果dp\[j-t\[i\]\]都不是最大价值，那么dp\[j\]肯定就不是最大价值。什么时候会出现这种情况，就是对dp\[j\]进行更新时，dp\[j-t\[i\]\]还没更新的时候。那怎么让dp\[j-t\[i\]\]先更新，由每个物品的更新区域我们可以看出，右边界是由**d**决定的，所以要想dp\[j-t\[i\]\]先更新，也就先用**d**小的物品进行更新。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<vector>
     3 #include<algorithm>
     4 using namespace std;
     5 struct Node{
     6     int val;
     7     vector<int> wp;
     8     Node(){
     9         val=0;
    10         wp.clear();//wp就记录下相应救下的是哪些物品 
    11     }
    12 }dp[2118],ans;
    13 struct Wp{
    14     int t,d,p,id;
    15     bool operator<(const Wp &w1)const{
    16         return d<w1.d;//按烧毁时间早的排 
    17     }
    18 }w[118];
    19 int main()
    20 {
    21     int n;
    22     scanf("%d",&n);
    23     for(int i=1;i<=n;i++)
    24     {
    25         w[i].id=i;
    26         scanf("%d%d%d",&w[i].t,&w[i].d,&w[i].p);
    27     }
    28     sort(w+1,w+1+n);
    29     for(int i=1;i<=n;i++)
    30     {
    31         for(int j=w[i].d-1;j>=w[i].t;j--)
    32         {
    33             if(dp[j].val<dp[j-w[i].t].val+w[i].p)//01背包的转移过程 
    34             {
    35                 dp[j].val=dp[j-w[i].t].val+w[i].p;
    36                 dp[j].wp=dp[j-w[i].t].wp;
    37                 dp[j].wp.push_back(w[i].id);
    38             }
    39         }
    40     }
    41     for(int i=0;i<=2000;i++)
    42         if(ans.val<dp[i].val)
    43             ans=dp[i];
    44     printf("%d\n%d\n",ans.val,ans.wp.size());
    45     for(int i=0;i<ans.wp.size();i++)
    46     {
    47         if(i)
    48             putchar(' ');
    49         printf("%d",ans.wp[i]);
    50     }
    51     return 0;
    52 }
    53 /*
    54 2
    55 1 3 2
    56 1 2 2
    57 */

背包要排序

不在dp里套用vector来记录路径的话，也可以记录下每个时间抢救过那些物品以及最后抢救的物品，然后进行回溯。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<vector>
     3 #include<algorithm>
     4 using namespace std;
     5 struct Wp{
     6     int t,d,p,id;
     7     bool operator<(const Wp &w1)const{
     8         return d<w1.d;//按烧毁时间早的排 
     9     }
    10 }w[118];
    11 int dp[2118],wp[2118],vis[118][2118];
    12 void dfs(int num,int i,int j)
    13 {
    14     if(!j)
    15     {
    16         printf("%d\n",num);
    17         return ;
    18     }
    19     if(!vis[i][j])//如果i这个物品没在j时间更新过答案，就看上一个物品 
    20         dfs(num,i-1,j);
    21     else
    22     {
    23         dfs(num+1,i-1,j-w[i].t);//否则减去i这个物品耗费的时间 
    24         printf("%d",w[i].id);
    25         if(i)
    26             putchar(' ');
    27     }
    28 }
    29 int main()
    30 {
    31     int n;
    32     scanf("%d",&n);
    33     for(int i=1;i<=n;i++)
    34     {
    35         w[i].id=i;
    36         scanf("%d%d%d",&w[i].t,&w[i].d,&w[i].p);
    37     }
    38     sort(w+1,w+1+n);
    39     for(int i=1;i<=n;i++)
    40     {
    41         for(int j=w[i].d-1;j>=w[i].t;j--)
    42         {
    43             if(dp[j]<dp[j-w[i].t]+w[i].p)//01背包的转移过程 
    44             {
    45                 dp[j]=dp[j-w[i].t]+w[i].p;
    46                 vis[i][j]=1;//标记下j时间使用过i物品来更新 
    47                 wp[j]=i;
    48             }
    49         }
    50     }
    51     int ans=0,j=0;
    52     for(int i=0;i<=2000;i++)
    53         if(ans<dp[i])
    54         {
    55             ans=dp[i];
    56             j=i;
    57         }
    58     printf("%d\n",ans);
    59     dfs(0,wp[j],j);
    60     return 0;
    61 }
    62 /*
    63 2
    64 1 3 2
    65 1 2 2
    66 */

回溯

**[CodeForces - 894C][][Marco and GCD Sequence][]**

题目大意：给你一个序列的所有子区间的gcd的set集合，问你能不能反过来构造出这个序列，不能的话输出-1，能的话输出构造的序列

嗯，一开始就觉得他给出的S序列就是答案，因为当l==r时的\[l,r\]子区间的gcd就是相应的数本身，所以只要判断所有数的gcd是不是最小的s0就好，因为最小那个数肯定是所有数的gcd。但这样有个问题，比如给出的序列是1 3 10 15，那么它们的gcd就应该还有个5，而不是单单这个序列。那怎么办呢，所有数肯定是最小的s0的倍数，那么每个数和s0的gcd肯定是s0，那么我们在每个数的前后都加上一个s0的话，这样对于每个数，除了l==r时的它的gcd为本身外，其他区间的gcd都等于s0，而不会产生新的gcd。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<algorithm>
     3 using namespace std;
     4 int a[1108];
     5 int main()
     6 {
     7     int n;
     8     scanf("%d",&n);
     9     for(int i=0;i<n;i++)
    10         scanf("%d",&a[i]);
    11     int g=0;
    12     for(int i=0;i<n;i++)
    13         g=__gcd(g,a[i]);
    14     if(g!=a[0])
    15         printf("-1\n");
    16     else
    17     {
    18         printf("%d\n",2*n+1);
    19         printf("%d",a[0]);
    20         for(int i=0;i<n;i++)
    21             printf(" %d %d",a[i],a[0]);
    22     }
    23     return 0;
    24 }

构造

**[CodeForces - 998D][][Roman Digits][]**

题目大意：I=1, V=5, X=10, L=50，对于一个字母序列，它的权值是所有字母权值之和，比如IXX的权值就是1+10+10=21，给你序列的长度，问组合多少个不同的权值。

没啥想法，就打表看了下，发现从长度是11后，每次长度+1,答案就+49，打表程序为注释部分。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<cstring>
     3 #include<cmath>
     4 using namespace std;
     5 typedef long long ll;
     6 const int a[4]={
         1,5,10,50};
     7 const ll ans[15]={
         1,4,10,20,35,56,83,116,155,198,244,292,341};
     8 //int n,ans,vis[1000000];
     9 //void dfs(int x,int sum)
    10 //{
    11 //    if(x==n)
    12 //    {
    13 //        if(!vis[sum])
    14 //        {
    15 //            ans++;
    16 //            vis[sum]=1;
    17 //        }
    18 //        return ;
    19 //    }
    20 //    for(int i=0;i<4;i++)
    21 //        dfs(x+1,sum+a[i]);        
    22 //}
    23 int main()
    24 {
    25     int n;
    26     while(~scanf("%d",&n))
    27     {
    28 //        ans=0;
    29 //        memset(vis,0,sizeof(vis));
    30 //        dfs(0,0); 
    31 //        printf("%d %d\n",ans,ans-ans2);
    32 //        ans2=ans;
    33         if(n<=12)
    34             printf("%lld\n",ans[n]);
    35         else
    36             printf("%lld\n",ans[12]+1ll*(n-12)*49ll); 
    37     }
    38     return 0;
    39 }

暴力打表

转载于:https://www.cnblogs.com/LMCC1108/p/10873801.html

[CodeForces - 864E]: https://cn.vjudge.net/problem/1091057/origin
[Fire]: https://cn.vjudge.net/problem/CodeForces-864E
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211119/673f0e170aae4eaa981b66fdd7b9c721.png
[CodeForces - 894C]: https://cn.vjudge.net/problem/1214117/origin
[Marco and GCD Sequence]: https://cn.vjudge.net/problem/CodeForces-894C
[CodeForces - 998D]: https://cn.vjudge.net/problem/1650600/origin
[Roman Digits]: https://cn.vjudge.net/problem/CodeForces-998D