Summary of the 16th week

1、Treats for the Cows G/S

P2858 [USACO06FEB]Treats for the Cows G/S - Luogu | New ecology of computer science education (luogu.com.cn)

The question ： There is a length of n Sequence of numbers , The number of the sequence i Items for a[i], In the j One day you can sell the leftmost or rightmost of the remaining series , Then your money will be added to the amount you sold ×j Product of , Only one can be sold per day , Find the maximum total amount of money

In order to exercise the ability of reading questions , I read this question on the valley of Los Angeles , Section dp Thought ： set up f[i][j] From i To j The optimal value , Then enumerate from a small interval to a large interval , Such a step-by-step selection , Finally, the f[1][n] Value .

int dfs(int l,int r,int d)
{
	if(r<l) return 0;
	if(l==r) return a[l]*d;
	if(f[l][r]) return f[l][r];
	f[l][r]=f[l][r]>dfs(l+1,r,d+1)+a[l]*d?f[l][r]:dfs(l+1,r,d+1)+a[l]*d;
	f[l][r]=f[l][r]>dfs(l,r-1,d+1)+a[r]*d?f[l][r]:dfs(l,r-1,d+1)+a[r]*d;
	  return f[l][r];
}

2、String painter

Problem - 2476 (hdu.edu.cn)

The question ： There are two strings , Now there is an operation to change an interval of the first string to the same letter , Ask at least how many steps can become the second string . Each speech can be defined by its start and end time , Do not repeat , Read in the start and end times of all speeches , Calculate the maximum possible total speech time

If direct dp once , Then there are two ways to transfer , The... Of the first string i And the second string i individual ,sum[i]=sum[i-1]. This is easier to understand . If it's not equal , if sum[i]=sum[i-1]+1, Clearly wrong , If you come to the i During the period , It can be modified together with one of the previous sections , Then it will be counted once more .

Enumerate directly the violence ,sum[i]=min(sum[i],sum[j]+d[j+1][i]）;j Range 0-i, So if each time is not equal , All of them are enumerated from the front .

 for(int i=1;i<=n;i++)
   {for(int l=0;l<n-i+1;l++)
     { int r=l+i-1;
       dp[l][r]=dp[l+1][r]+1;
       for(int k=l+1;k<=r;k++)
       { if(b[l]==b[k])
          dp[l][r]=min(dp[l+1][k]+dp[k+1][r],dp[l][r]);}}}
 for(int i=0;i<n;i++)
  {sum[i]=dp[0][i];}
 for(int i=0;i<n;i++)
  {if(a[i]==b[i];
    {sum[i]=sum[i-1];}
   else
    {for(int j=0;j<=i;j++)
       {sum[i]=min(sum[j]+dp[j+1][i],sum[i]);}}}

3、 Ladder classroom equipment utilization  P2439 [SDOI2005] Ladder classroom equipment utilization - Luogu | New ecology of computer science education (luogu.com.cn)

The question ： Each speech can be defined by its start and end time , Do not repeat , Read in the start and end times of all speeches , Calculate the maximum possible total speech time . 

This problem is similar to the problem of arranging work before , Let's start by sorting the speeches from small to large according to the ending time , And then use dp, Clear thinking , But the data is big , My mind is in a mess again , I read some big guy's solutions , Put it together , Only then dp The equation is written , But the rest of the code is not yet complete , So this question has not been submitted yet .

f[i] Express 1~i The longest time that can be used ,j Indicates that the end time is i Speech ,n For the number of all speeches
The equation of state transfer is ：f[i]=max(f[i-1],f[a[j].begin-1]+a[j].end-a[j].begin+1)
The answer for ：f[a[n].end]

        This is the last weekly summary blog of this semester , So I chose three questions to solve , The rest would like to briefly summarize the experience of this semester and this course . At first our class schedule had this course , Later, because it was an elective course , Many people have cancelled their choice , I think why not try it . Later in the learning process , I really feel the difficulty and time of this course , I even thought about it in the middle of the semester , If I didn't choose this course , How will I spend my freshman semester ？ And the turning point of dispelling this idea , After I took part in a provincial competition , I suddenly found that I liked the atmosphere , Like to enjoy the long race time that requires concentration , I like the busy before and after the game and the feeling of fighting side by side with my teammates and teachers , I don't think I regret choosing this one .

        I'm glad I had such an experience , Also want to continue to enjoy the game in the future , steel oneself , Enrich yourself , Improve yourself , And learning ACM In the process of , Learn to learn , Learn to dynamically plan your life . come on. ！