第九周学习体会

学习体会"/>

第九周学习体会

这个周我做了区间dp和背包的有关练习，感觉对他们有了最初步的了解，今天下午打算在csdn上继续找些这方面的问题加深对这方面的理解。另外我们又学了二分法的有关知识，他是一个函数在定义域内单调有根，通过将根区间不断等分寻找近似解或精确解的方法。这次对于二分法的练习，我一定会合理分配练习时间，不能再像上次线性dp的训练一样拖到快结束的时候在集中做。

二分法算法步骤
步骤1： 准备 计算f(x)在有根区间[a,b]端点处的值f(a)，f(b)。
步骤2： 二分 计算f(x)在区间中点 (a+b)/2处的值 f((a+b)/2)。
步骤3： 判断 若f((a+b)/2)=0，则(a+b)/2即是根，计算过程结束，否则检验；若f((a+b)/2)f(a)<0，则以(a+b)/2代替b，否则以(a+b)/2代替a。
反复执行步骤2和步骤3，直到区间[a,b]的长度小于允许误差e，此时中点(a+b)/2即为所求近似根。

另外这个周打了两次codeforces的比赛，可能是第一次进行这样的比赛，感觉对这样的比赛不是很适应，对于以后进行的比赛我争取做到dive 2和dive 3的比赛全部参加，然后比赛结束第二天对我本来可以解决但是没有做出来的题目进行分析。

题目
1.饭卡
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
Input
多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。

n=0表示数据结束。
Output
对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。
Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
Sample Output
-45
32

对于这道题我们应该先将价格进行升序排序，然后保留第n-1个数据最后进行处理，在m-5的背包里尽量放置更多的菜，状态转移方程：dp[j]=max(dp[j],dp[j-a[i]]+a[i])，求出最大的dp[m-5],然后用m-dp[m-5]-a[n-1]就能得出最后饭卡里剩余的最少钱数。

ac代码：

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1001
bool cmp(int a,int b)
{return a<b;
}
int dp[N],a[N];
int main()
{int n,m;while(cin>>n){if(n==0) break;for(int i=0;i<n;i++)cin>>a[i];cin>>m;memset(dp,0,sizeof(dp));sort(a,a+n,cmp);if(m<5){cout<<m<<endl;}else{for(int i=0;i<n-1;i++){for(int j=m-5;j>=a[i];j--)dp[j]=max(dp[j],dp[j-a[i]]+a[i]);}cout<<m-dp[m-5]-a[n-1]<<endl;}}return 0;
}

2.Dire wolves
Dire wolves, also known as Dark wolves, are extraordinarily large and powerful wolves. Many, if not all, Dire Wolves appear to originate from Draenor.
Dire wolves look like normal wolves, but these creatures are of nearly twice the size. These powerful beasts, 8 - 9 feet long and weighing 600 - 800 pounds, are the most well-known orc mounts. As tall as a man, these great wolves have long tusked jaws that look like they could snap an iron bar. They have burning red eyes. Dire wolves are mottled gray or black in color. Dire wolves thrive in the northern regions of Kalimdor and in Mulgore.
Dire wolves are efficient pack hunters that kill anything they catch. They prefer to attack in packs, surrounding and flanking a foe when they can.
— Wowpedia, Your wiki guide to the World of Warcra

Matt, an adventurer from the Eastern Kingdoms, meets a pack of dire wolves. There are N wolves standing in a row (numbered with 1 to N from left to right). Matt has to defeat all of them to survive.

Once Matt defeats a dire wolf, he will take some damage which is equal to the wolf’s current attack. As gregarious beasts, each dire wolf i can increase its adjacent wolves’ attack by b i. Thus, each dire wolf i’s current attack consists of two parts, its basic attack ai and the extra attack provided by the current adjacent wolves. The increase of attack is temporary. Once a wolf is defeated, its adjacent wolves will no longer get extra attack from it. However, these two wolves (if exist) will become adjacent to each other now.

For example, suppose there are 3 dire wolves standing in a row, whose basic attacks ai are (3, 5, 7), respectively. The extra attacks b i they can provide are (8, 2, 0). Thus, the current attacks of them are (5, 13, 9). If Matt defeats the second wolf first, he will get 13 points of damage and the alive wolves’ current attacks become (3, 15).

As an alert and resourceful adventurer, Matt can decide the order of the dire wolves he defeats. Therefore, he wants to know the least damage he has to take to defeat all the wolves.
Input
The first line contains only one integer T , which indicates the number of test cases. For each test case, the first line contains only one integer N (2 ≤ N ≤ 200).

The second line contains N integers a i (0 ≤ a i ≤ 100000), denoting the basic attack of each dire wolf.

The third line contains N integers b i (0 ≤ b i ≤ 50000), denoting the extra attack each dire wolf can provide.
Output
For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1), y is the least damage Matt needs to take.
Sample Input
2
3
3 5 7
8 2 0
10
1 3 5 7 9 2 4 6 8 10
9 4 1 2 1 2 1 4 5 1
Sample Output
Case #1: 17
Case #2: 74

这道题采用了区间dp的解题方法，按照线性dp的基本模板

for(int len=1;len<=n;len++)
for(int i=1;i<=n-len+1;i++)
int j=i+len-1;
for(int k=i;k<=j;k++)
套好之后我们可以写出状态转移方程dp[i][j]=min(dp[i][j],dp[i][k-1]+a[k]+dp[k+1][j]+b[i-1]+b[j+1])，然后直接输出dp[1][n]的取值即可。

ac代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
#define N 201
using namespace std;
int a[N],b[N],dp[N][N];
int main()
{int t,num=1;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];b[0]=b[n+1]=0;memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)dp[i][j]=inf;for(int len=1;len<=n;len++){for(int i=1;i<=n-len+1;i++){int j=i+len-1;for(int k=i;k<=j;k++)dp[i][j]=min(dp[i][j],dp[i][k-1]+a[k]+dp[k+1][j]+b[i-1]+b[j+1]);}}cout<<"Case #"<<num++<<": "<<dp[1][n]<<endl;}return 0;
}

生死看淡，不服就干