第9周训练总结（4.26）

第9周训练总结（4.26）

这周的区间DP做了几道题之后还是理解的不太透彻，至于背包问题，可能因为太多模板的味道在里面，相比于区间和线性来说要简单许多。

这周又是两场CF，仍然是一场Div3一场Div2的，但不幸的是和上周相反，Div3的做出来两道，而Div2的一道没做出来，对于Div2的那场来说，感觉前两道不是太难，但就是过不了第二个样例点，哎，功夫还是不到家啊。

这次总结主要针对区间DP，和背包问题的一部分，主要是区间DP。

区间DP

废话不多，上题

When we are focusing on solving problems, we usually prefer to stay in front of computers rather than go out for lunch. At this time, we may call for food delivery.

Suppose there are N people living in a straight street that is just lies on an X-coordinate axis. The ith person's coordinate is Xi meters. And in the street there is a take-out restaurant which has coordinates X meters. One day at lunchtime, each person takes an order from the restaurant at the same time. As a worker in the restaurant, you need to start from the restaurant, send food to the N people, and then come back to the restaurant. Your speed is V-1 meters per minute.

You know that the N people have different personal characters; therefore they have different feeling on the time their food arrives. Their feelings are measured by Displeasure Index. At the beginning, the Displeasure Index for each person is 0. When waiting for the food, the ith person will gain Bi Displeasure Index per minute.

If one's Displeasure Index goes too high, he will not buy your food any more. So you need to keep the sum of all people's Displeasure Index as low as possible in order to maximize your income. Your task is to find the minimal sum of Displeasure Index.

Input

The input contains multiple test cases, separated with a blank line. Each case is started with three integers N ( 1 <= N <= 1000 ), V ( V > 0), X ( X >= 0 ), then N lines followed. Each line contains two integers Xi ( Xi >= 0 ), Bi ( Bi >= 0), which are described above.

You can safely assume that all numbers in the input and output will be less than 231 - 1.

Please process to the end-of-file.

Output

For each test case please output a single number, which is the minimal sum of Displeasure Index. One test case per line.

Sample Input

5 1 0
1 1
2 2
3 3
4 4
5 5
 

Sample Output

55

 一个店送外卖，顾客有不开心值，每多等一分钟又会加一个数，问你送完所有外卖最小不开心值

思路分析：

一道比较特别的区间DP问题，显然对于一个区间内是有方向的，比如从i->j，还是j->i，虽然一开始我也不知道，但知道了这个以后，很容易结合区间DP模板写出

dp[i][j][[0]表示送完[i,j]区间停在左边（i），dp[i][j][1]表示送完[i,j]区间停在右边（j）。

 

对于停在i处可能由i+1处回来，也可能由j处回来，其他同理

所以试着写出dp[i][j][0]=dp[i+1][j][0]+x

其中X是，（从i+1到i坐标去时的距离s）与（除i--j区间内客人不满意值的增加量）的乘积

或dp[i][j][0]=dp[i+1][j][1]+x

此时x是，（从j到i坐标去时的距离s）与（除i--j区间内客人不满意值的增加量）的乘积

这真是一道好题

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
#define rush() int T;cin>>T;while(T--)
#define sf(a) scanf("%d\n",&a)
#define sft(a,b) scanf("%d%d",&a,&b)
#define go(a) while(scanf("%d",&a)!=EOF)
#define ms(a,b) memset(a,b,sizeof a)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pf(a) printf("%.8lf",a)
#define E 1e-8
using namespace std;
typedef long long ll;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const int idata=1e3+5;int n,m,t,f;
int i,j,k;
int a[idata];
int dp[idata][idata][2];
int sum[idata];struct node
{int cord,delta;bool operator<(const node &b){return cord<b.cord;}
}node[idata];int main()
{cin.tie(0);iostream::sync_with_stdio(false);while(cin>>n>>m>>f){ms(dp,0x7f);for(i=1;i<=n;i++){cin>>node[i].cord>>node[i].delta;}sort(node+1,node+n+1);for(i=1;i<=n;i++){sum[i]=sum[i-1]+node[i].delta;}for(i=1;i<=n;i++){dp[i][i][0]=dp[i][i][1]=abs(node[i].cord-f)*sum[n];}for(int len=2;len<=n;len++){for(i=1,j=len;j<=n;i++,j++){停在i处可能由i+1处回来，也可能由j处回来，其他同理dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+abs(node[i+1].cord-node[i].cord)*(sum[n]-sum[j]+sum[i]));dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+abs(node[j].cord-node[i].cord)*(sum[n]-sum[j]+sum[i]));dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+abs(node[j].cord-node[i].cord)*(sum[n]-sum[j-1]+sum[i-1]));dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+abs(node[j].cord-node[j-1].cord)*(sum[n]-sum[j-1]+sum[i-1]));}}cout<<min(dp[1][n][0],dp[1][n][1])*m<<endl;}return 0;
}

/*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

Hint

In the first sample, Matt defeats the dire wolves from left to right. He takes 5 + 5 + 7 = 17 points of damage which is the least damage he has to take.

大致题意：  有一排狼，堵在路上，每头狼都有一定的攻击力，而且除了首尾的狼外，你每次攻击任何一头狼，受的伤害处理该狼的攻击力外，还有与该狼相邻的狼的额外攻击力，而首尾的狼的额外攻击力只有来自右边的和左边的狼，现在你要杀掉所有的狼，并使自己受到的伤害值最小，求伤害值。 

 对于这个题目来说，最大的不同，就是多了一重循环，来枚举各个间断点，典型的三部

1.区间长度，由小到大。

2.区间起点，由小到大

3.枚举区间中的分界点，区分左右区间。

虽然很多人看来是道模板题，但是为什么会出现三重循环，也就是说为什么要枚举区间内的间断点呢？

因为与上一道题不同，上一道题只考虑端点，而这个题去区间端点发生改变，影响了内部，所以区间内也要发生改变，这边是本人的一点拙见

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstring>
#define rush() int T;cin>>T;while(T--)
#define sf(a) scanf("%d\n",&a)
#define sft(a,b) scanf("%d%d",&a,&b)
#define go(a) while(cin>>a&&a)
#define ms(a,b) memset(a,b,sizeof a)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pf(a) printf("%.8lf",a)
#define leth first
#define extra second
#define E 1e-8
using namespace std;
typedef long long ll;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const int idata=200+5;int n,m,t;
int maxx,minn,ans;
int i,j,k;
int dp[idata][idata];
pair<int,int>p[idata];int main()
{cin.tie(0);iostream::sync_with_stdio(false);rush(){cin>>n;for(i=1;i<=n;i++) cin>>p[i].leth;for(i=1;i<=n;i++) cin>>p[i].extra;p[0].leth=p[0].extra=p[n+1].leth=p[n+1].extra=0;//区间初始化for(i=1;i<=n;i++) dp[i][i]=p[i].leth+p[i-1].extra+p[i+1].extra;for(int len=2;len<=n;len++)//区间长度{for(i=1,j=len;j<=n;j++,i++)//起点终点{//最后杀区间端点上的狼dp[i][j]=min(dp[i+1][j]+p[i].leth+p[i-1].extra+p[j+1].extra,dp[i][j-1]+p[j].leth+p[j+1].extra+p[i-1].extra);//区间内进行更新for(k=i;k<j;k++){dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+p[k].leth+p[i-1].extra+p[j+1].extra);}}}printf("Case #%d: %d\n",++ans,dp[1][n]);}return 0;
}

 

 

 背包问题

 

Battle Ships is a new game which is similar to Star Craft. In this game, the enemy builds a defense tower, which has L longevity. The player has a military factory, which can produce N kinds of battle ships. The factory takes ti seconds to produce the i-th battle ship and this battle ship can make the tower loss li longevity every second when it has been produced. If the longevity of the tower lower than or equal to 0, the player wins. Notice that at each time, the factory can choose only one kind of battle ships to produce or do nothing. And producing more than one battle ships of the same kind is acceptable.

Your job is to find out the minimum time the player should spend to win the game.

Input

There are multiple test cases.
The first line of each case contains two integers N(1 ≤ N ≤ 30) and L(1 ≤ L ≤ 330), N is the number of the kinds of Battle Ships, L is the longevity of the Defense Tower. Then the following N lines, each line contains two integers t i(1 ≤ t i ≤ 20) and li(1 ≤ li ≤ 330) indicating the produce time and the lethality of the i-th kind Battle Ships.

Output

Output one line for each test case. An integer indicating the minimum time the player should spend to win the game.

Sample Input

1 1
1 1
2 10
1 1
2 5
3 100
1 10
3 20
10 100

Sample Output

2
4
5

 

一开始拿到这个题，真心不知道怎么下手，但是问题是这里每艘船在生产出来后每一秒都对塔造成伤害，但DP问题不能有后效性，就是对各个子问题寻求最优解，但是这题怎么才能做到无后效性呢？

 

问题很显然是一个完全背包问题，但要解决后效性的问题，最后还是要靠大家的力量

dp[j]=max(dp[j],dp[j-p[i].tim]+(j-p[i].tim)*p[i].leth);

一开始还以为这是错误答案，但后来发现自己是真的太弱了，对于一个问题的想法有限。这点，在CF和新生赛的时候深有体会，

这个状态转移方程怎么来的？我们总是习惯背包的模式，一个背包叠加一个背包，减掉一个背包重量再加上一个背包价值，但是背包的前置和后置是没有关系的，而这题却不是

 

所以在第i种船的建造时，我们肯定将这第i种船添加到最前面去生产，然后乘以时间（减去生产时间）加上减去生产时间所能造成最大伤害与该时间的伤害比较，就能得出结果了。

 

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstring>
#define rush() int T;cin>>T;while(T--)
#define sf(a) scanf("%d\n",&a)
#define sft(a,b) scanf("%d%d",&a,&b)
#define go(a) while(cin>>a&&a)
#define ms(a,b) memset(a,b,sizeof a)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pf(a) printf("%.8lf",a)
#define tim first
#define leth second
#define E 1e-8
using namespace std;
typedef long long ll;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const int idata=1e3+5;int n,m,t;
int maxx,minn;
int i,j,k;
int a[idata],dp[idata];
pair<int,int>p[idata];int main()
{cin.tie(0);iostream::sync_with_stdio(false);while(cin>>n>>m){for(i=1;i<=n;i++){cin>>p[i].tim>>p[i].leth;}minn=inf,ms(dp,0);for(i=1;i<=n;i++){for(j=p[i].tim;;j++){//必须在动态转移方程上面表达题目状态转移的意思dp[j]=max(dp[j],dp[j-p[i].tim]+(j-p[i].tim)*p[i].leth);  if(dp[j]>=m) break;}minn=min(minn,j);}cout<<minn<<endl;}return 0;
}

对于但是CF比赛来说，至少我知道每个题目的解法都是思路的一个体现，而思路大多是从一个人看事物的方式决定的，我觉得可能多看书，多理解，多发掘，可能对于这部分能力会有所提升，总之多看书，多打码）