第十六周总结

1、Treats for the Cows G/S

P2858 [USACO06FEB]Treats for the Cows G/S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：有一个长度为n的数列，数列的第i项为a[i]，在第j天你可以卖掉目前剩下的数列的最左边或者最右边，这时你的钱就会加上你卖掉的数×j的积，每一天只能卖一个，求最大的总钱数

为了锻炼一下读题能力，在洛谷上看了这道题，区间dp的思想：设f[i][j]表示从i到j的最优值，然后由一个小的区间枚举到一个大的区间，这样一步一步的选，最终求出f[1][n]的值。

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)

题意：有两个字符串，现在有一个操作可以把第一个字符串的某区间改成同一个字母，问最少多少步可以变成第二个字符串。每一个演讲都可以用起始和终止时间来确定，不可重复，读入所有演讲的起始和终止时间，计算最大的可能演讲总时间

如果直接dp一下，那么会有在两种转移方式，第一个字符串的第i个和第二个字符串的第i个，sum[i]=sum[i-1].这个比较容易理解。如果不相等，若为sum[i]=sum[i-1]+1,显然是错误的，如果到第i段的时候，可以和前面的某一部分一起修改，那么就会多算一次。

直接暴力枚举一下，sum[i]=min(sum[i],sum[j]+d[j+1][i]）；j 范围0-i，这样若每次不相等，都从前面枚举一遍。

 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、阶梯教室设备利用 P2439 [SDOI2005]阶梯教室设备利用 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：每一个演讲都可以用起始和终止时间来确定，不可重复，读入所有演讲的起始和终止时间，计算最大的可能演讲总时间。 

这个题与之前安排工作的题相似，我们先按结束时间从小到大把演讲排序，然后再用dp，思路明确，但数据一大，头绪又乱掉了，看了一些大佬的题解，拼拼凑凑，才把dp方程写了出来，但代码其余部分还未完成，所以这个题还没有尝试提交。

f[i]表示1~i时间能够利用的最长时间，j表示结束时间是i的演讲，n为所有演讲的数目
状态转移方程为：f[i]=max(f[i-1],f[a[j].begin-1]+a[j].end-a[j].begin+1)
答案为：f[a[n].end]

        这是这学期最后一次周总结博客，所以选择了三道题解，剩余的想简单总结一下这个学期以及这门课的体会。最初我们班的课表有这门课，后来因为是选修，很多人取消了选择，我想这何不尝试一下呢。后来在学习过程中，确实也真真正正的感受到了这门课的难度与所需要付出的时间，在学期期中的时候甚至想过，如果我没选择这门课，我的大一下学期会怎样过呢？而打消这个想法的转折点，是我参加了一次省赛之后，我突然发现我喜欢上了这种氛围，喜欢享受需要聚精会神却漫长的比赛时间，喜欢比赛前后的忙碌和与队友以及老师并肩作战的感觉，我认为我选择了这个是不后悔的。

       我庆幸自己能有这样的经历，也想在以后继续享受比赛，锻炼自己，丰富自己，提升自己，并在学习ACM的过程中，学会学习，学会动态规划生活。加油！