首页 > ACM题库 > HDU-杭电 > HDU 4395-D-mail-动态规划-[解题报告]HOJ
2015
05-24

HDU 4395-D-mail-动态规划-[解题报告]HOJ

D-mail

问题描述 :

To control the world, which is the ambition of Ryntarou Okabe, a mad scientist, is a problem that both of technology and wisdom are needed to handle it. After long time of experiment, Okabe eventually invented a strange machine, Telephone Oven, which can be used to send mails to the past! The mail is called D-mail in short. D-mail can be used to change the future of the world, but it cannot change it as what Okabe thinks exactly. According to the theory of time travel, the future of the world can be described by a real number, which is called Divergence. Now, Okabe has already calculated the Divergence that represents the world in which Okabe takes the control of the whole world. He calls it Steins Gate. There are kinds of D-mails with different content. And he has got the influence each kind of D-mail has to the Divergence. Now he wants to change the Divergence to a number as close to the Steins Gate as possible by selecting several kinds of D-mail, while each kind of D-mail cannot be used more than once. (He can choose 0 D-mail.)
Digital Square

But if he changes the divergence too greatly that it becomes bigger than 2 or equals 2 during the process he send D-mail, then will he be trapped in the infinity maze of time and be "corrected" by the world itself, so he should choose the best order to send the D-mail so as to keep alive before he achieves his goal. Can you help him calculate the best result he can get? The original Divergence is 0.

输入:

The first line contains an integer T, which represents the number of test cases.
For each test, the first line contains a real number D (-1<D<2), Stains Gate and an integer N(0<N<=200 ),represents the number of the kinds of D-mails. For the next N lines, each line contains a real number (which is no lesser than -0.1 and no bigger than 2)showing the influence of this D-mail to the Divergence. (all real number in the input file are written with exactly four digits after a decimal point.)

输出:

The first line contains an integer T, which represents the number of test cases.
For each test, the first line contains a real number D (-1<D<2), Stains Gate and an integer N(0<N<=200 ),represents the number of the kinds of D-mails. For the next N lines, each line contains a real number (which is no lesser than -0.1 and no bigger than 2)showing the influence of this D-mail to the Divergence. (all real number in the input file are written with exactly four digits after a decimal point.)

样例输入:

2
0.1234 2
0.1211
0.0023
-0.1234 2
0.1211
0.0023

样例输出:

0.1234
0.0000

题目链接:Click here~~

题意:

给 n 个数字,选取一些取它们的和 S,取和的过程中 S 不能超过2,求出最接近目标数字 D 的 S。(数字均为 4 位小数)

解题思路:

很明显的 dp 模型,状态 dp[i][j] 表示前 i 个数字是否能取到和为 j 的情况。

由于条件的限制,第一维可以滚动,第二维的有效区间为 [-20,2] , 映射成整数是 [-200000,20000],再向右平移得到 [0,220000]。

由于 “取和的过程中 S 不能超过2” ,那么采取贪心的策略,先取小的,即对 w 排序后再 dp。

需要注意的是:1、double 转 int 时还要加个 eps。 2、由于使用了滚动数组,当 w[i] 为负数时 循环的方向要改变。

思路明朗后,代码也不难。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 2e5 + 2e4;

const int shift = 2e5;

bool reach[N];

int w[205];

inline int read(){
    double x;
    scanf("%lf",&x);
    if(x > 0)
        return x * 10000 + 1e-8;
    else
        return x * 10000 - 1e-8;
}

int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        memset(reach,false,sizeof(reach));
        int goal = read();
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            w[i] = read();
        sort(w,w+n);
        reach[ 0 + shift ] = true;
        for(int i=0;i<n;i++)
        {
            bool f = w[i] > 0;
            if(f)
            {
                for(int j=N-1-w[i];j>=0;j--)
                    if(reach[j])
                        reach[ j + w[i] ] = true;
            }
            else
            {
                for(int j=-w[i];j<N;j++)
                    if(reach[j])
                        reach[ j + w[i] ] = true;
            }
        }
        int i = goal + shift , j = 0;
        int ans = -1;
        while(1)
        {
            if(i-j >= 0 && reach[i-j])
            {
                ans = i - j;
                break;
            }
            if(i+j < N && reach[i+j])
            {
                ans = i + j;
                break;
            }
            ++j;
        }
        printf("%.4f\n",(ans-shift)/10000.0);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/dgq8211/article/details/12746797