Bone Collector

Description:

Input

Output

Sample Input
1
10 10
1 3 5 7 9 11 13 15 17 19
19 17 15 13 11 9 7 5 3 1
Sample Output
51

Problem solving:

01背包问题，直接套板子即可

Code:

#include<bits/stdc++.h>
using namespace std;
const int tx=1e6;
int m[tx],M[tx],dp[tx];
int main()
{
int t,n,s;
cin>>t;
while(t--)
{
cin>>n>>s;
for(int i=0;i<n;i++)    cin>>m[i];
for(int i=0;i<n;i++)    cin>>M[i];
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
{
for(int j=s;j>=M[i];j--)
{
dp[j]=max(dp[j],dp[j-M[i]]+m[i]);
}
}
cout<<dp[s]<<endl;
}
}


饭卡

Description:

Input

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

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
const int tx=1005;
int m[tx],dp[tx];
int main()
{
int t,n;
while(cin>>t&&t)
{
memset(dp,0,sizeof(dp));
for(int i=0;i<t;i++)    cin>>m[i];
cin>>n;
if(n<5)
{
cout<<n<<endl;
continue;
}
sort(m,m+t);
for(int i=0;i<t-1;i++)
for(int j=n-5;j>=m[i];j--)
{
dp[j]=max(dp[j],dp[j-m[i]]+m[i]);
}
cout<<n-dp[n-5]-m[t-1]<<endl;
}
}


CD

Description:
PDF题面:戳我戳我
You have a long drive by car ahead. You have a tape recorder, but unfortunately your best music is on
CDs. You need to have it on tapes so the problem to solve is: you have a tape N minutes long. How
to choose tracks from CD to get most out of tape space and have as short unused space as possible.
Assumptions:
• number of tracks on the CD does not exceed 20
• no track is longer than N minutes
• tracks do not repeat
• length of each track is expressed as an integer number
• N is also integer
Program should find the set of tracks which fills the tape best and print it in the same sequence as
the tracks are stored on the CD
Input

Any number of lines. Each one contains value N, (after space) number of tracks and durations of the
tracks. For example from first line in sample data: N = 5, number of tracks=3, first track lasts for 1
minute, second one 3 minutes, next one 4 minutes

Output

Set of tracks (and durations) which are the correct solutions and string ‘sum:’ and sum of duration
times.

Sample Input

5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2

Sample Output

1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m,num;
const int maxn=10005;
int a[maxn],dp[maxn],flag[maxn][maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
while(cin>>n>>m)
{
for(int i=0;i<m;i++)    cin>>a[i];
memset(flag,0,sizeof(flag));
memset(dp,0,sizeof(dp));
for(int i=m-1;i>=0;i--)//这里倒序主要是在输出的时候方便
{
for(int j=n;j>=a[i];j--)
{
if(dp[j]<dp[j-a[i]]+a[i])//选上了a[i]的情况
{
dp[j]=dp[j-a[i]]+a[i];
flag[i][j]=1;//进行标记
}
}
}
for(int i=0,j=n;i<m;i++)
{
if(flag[i][j])//标价到的就输出
{
cout<<a[i]<<" ";
j-=a[i];
}
}
cout<<"sum:"<<dp[n]<<endl;
}
}


Piggy-Bank

Description:

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.

Problem solving:

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int p[505],w[505],dp[10005];
const int INF = 0x3f3f3f3f;
int main()
{
int t,s,e,n,cs;
cin>>t;
while(t--)
{
cin>>s>>e>>n;
cs=e-s;
for(int i=0;i<=cs;i++)    dp[i]=INF;
for(int i=0;i<n;i++)    cin>>p[i]>>w[i];
dp[0]=0;
for(int i=0;i<n;i++)
{
for(int j=w[i];j<=cs;j++)
{
dp[j]=min(dp[j],dp[j-w[i]]+p[i]);
}
}
if(dp[cs]!=INF)
cout<<"The minimum amount of money in the piggy-bank is "<<dp[cs]<<".";
else    cout<<"This is impossible.";
puts("");
}
}


Dividing coins

Description:
PDF题面：戳我戳我
It’s commonly known that the Dutch have invented copper-wire. Two Dutch men were fighting over
a nickel, which was made of copper. They were both so eager to get it and the fighting was so fierce,
they stretched the coin to great length and thus created copper-wire.
Not commonly known is that the fighting started, after the two Dutch tried to divide a bag with
coins between the two of them. The contents of the bag appeared not to be equally divisible. The Dutch
of the past couldn’t stand the fact that a division should favour one of them and they always wanted
a fair share to the very last cent. Nowadays fighting over a single cent will not be seen anymore, but
being capable of making an equal division as fair as possible is something that will remain important
forever...
That’s what this whole problem is about. Not everyone is capable of seeing instantly what’s the
most fair division of a bag of coins between two persons. Your help is asked to solve this problem.
Given a bag with a maximum of 100 coins, determine the most fair division between two persons.
This means that the difference between the amount each person obtains should be minimised. The
value of a coin varies from 1 cent to 500 cents. It’s not allowed to split a single coin.
Input

A line with the number of problems n, followed by n times:
• a line with a non negative integer m (m ≤ 100) indicating the number of coins in the bag
• a line with m numbers separated by one space, each number indicates the value of a coin.

Output

The output consists of n lines. Each line contains the minimal positive difference between the amount
the two persons obtain when they divide the coins from the corresponding bag.

Sample Input

2
3
2 3 5
4
1 2 4 6

Sample Output

0
1

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
const int tx=1e5+10;
int m[tx],dp[tx];
int main()
{
int n,t;
cin>>n;
while(n--)
{
cin>>t;
memset(dp,0,sizeof(dp));
int sum=0;
for(int i=0;i<t;i++)    cin>>m[i],sum+=m[i];
for(int i=0;i<t;i++)
{
for(int j=sum/2;j>=m[i];j--)
{
dp[j]=max(dp[j],dp[j-m[i]]+m[i]);
}
}
cout<<sum-dp[sum/2]-dp[sum/2]<<endl;
}
return 0;
}


Robberies

Description:

Input

Output

Notes and Constraints
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0

Sample Input

3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05

Sample Output

2
4
6

Problem solving:

dp[i]表示的就是偷了i美金之后不被抓的概率

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int m[maxn];double dp[100005],p[maxn];
int main()
{
ios::sync_with_stdio(0);
int t;
cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));
double pp;int n,sum=0;
cin>>pp>>n;
for(int i=0;i<n;i++)
{
cin>>m[i]>>p[i];
sum+=m[i];
p[i]=1-p[i];
}
dp[0]=1;//这个初始化很重要
for(int i=0;i<n;i++)
{
for(int j=sum;j>=m[i];j--)
{
dp[j]=max(dp[j],dp[j-m[i]]*p[i]);
}
}
for(int i=sum;i>=0;i--)
{
if(dp[i]>=1-pp)
{
cout<<i<<endl;
break;
}
}
}
return 0;
}


Coin Change

Description:
PDF题面:戳我戳我
Suppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make
changes with these coins for a given amount of money.
For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent
coin, two 5-cent coins and one 1-cent coin, one 5-cent coin and six 1-cent coins, or eleven 1-cent coins.
So there are four ways of making changes for 11 cents with the above coins. Note that we count that
there is one way of making change for zero cent.
Write a program to find the total number of different ways of making changes for any amount of
money in cents. Your program should be able to handle up to 7489 cents.
Input

The input file contains any number of lines, each one consisting of a number for the amount of money
in cents.

Output

For each input line, output a line containing the number of different ways of making changes with the
above 5 types of coins.

Sample Input

11
26

Sample Output

4
13

Problem solving:

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans[7500];
ll solve(ll x)
{
if(ans[x])    return ans[x];
int coins[13]  = { 1, 5, 10, 25, 50};
ll  dp[100005] = { 0 };
dp[0] = 1;
for (int i = 0; i < 6; i++)
{
for (int j = coins[i]; j <= x; j++)
{
dp[j] = dp[j] + dp[j - coins[i]];
}
}
return ans[x]=dp[x];
}
int main()
{
ll t, a;
ios::sync_with_stdio(0);
cin.tie(0);
while (cin >> a)
{
cout << solve(a)/2 << endl;
}
}


悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

Description:

Input

Output

Sample Input

1
8 2
2 100 4
4 100 2

Sample Output

400

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
const int tx=1e3;
int m[tx],p[tx],h[tx],c[tx];
int main()
{
int t,n,x;
cin>>t;
while(t--)
{
cin>>n>>x;
memset(m,0,sizeof(m));
for(int i=0;i<x;i++)    cin>>p[i]>>h[i]>>c[i];
for(int i=0;i<x;i++)
{
int mid=c[i];
for(int k=1;mid>0;k*=2)
{
int miid=min(k,mid);
for(int j=n;j>=p[i]*miid;j--)
{
m[j]=max(m[j],m[j-p[i]*miid]+h[i]*miid);
}
mid-=miid;
}
}
cout<<m[n]<<endl;
}
return 0;
}