求概率的系数的一个问题的求解,利用C语言的程序的设计的方式怎么做的

Problem Description
As the chief consultant in the International Consulting Company, you’re now enjoying such a high reputation in the industry that even the organizations underworld often come to you and ask for your suggestions. Professional as you are to your clients, you always try your best to help them and, certainly, make more profits for yourself. Money makes the mare go, and you’re no exception either.

But the shareholders of the company are always watching their profits as well. In order to protect the investors, they keep focusing on every project you take charge of. Once you receive money in a project, they will come immediately to you. If your profit is less than M dollars, they won’t step in; but if the profit reaches M , they will meddle in and take away profits in unit of M as much as possible. (e.g. if you earn (2M + 1) or exactly 2M dollars, they will both take 2M away.)

Now a big client comes. A famous robbery organization expects you to help them construct a robbery plan. The offer is so irresistible that you accept it immediately.

Their targets are the banks in the city. Totally, there’re K banks (numbered from 1 to K) that located at different areas, which produce different difficulties to rob them. The robbery team is made up of N people, and they have totally Q dollars as action funds. In a robbery, if they send p people and spend d dollars of funds to rob bank i, they will earn fi[p, d] in this action. Here, fi[p, d] is generated by
fi[p, d] =0 (p <= 0 or d <= 0)
fi[p, d] = fi[p - 1, d - ei] + fip - 1, d
and fi[1, d] comes from
fi[1, d] = Aif2i[1, d - 1] + Bifi[1, d - 1] + Ci (1 <= d <= Q)
where ei, Ai, Bi, Ci are coefficients given initially.

The team is so professional (as you are) that the members always succeed in robberies. After they rob a bank and get the money, the team will divide it into (almost) equal parts and distribute them to you and everyone who participates in this action. That is, if they send p men and rob X dollars, you’ll receive dollars immediately after the robbery on this bank. But at the time you receive the money, the damned shareholders will come and take away the part of theirs. Only the remaining part belongs to you.

You’re now required to help them determine the plan. Note that the robberies won’t take place simultaneously; and thus each person can rob several banks, but each bank can be robbed at most once (if we choose to rob it). The money they rob won’t be added to their action funds afterwards. Your final profit equals to the sum of profits that belongs to you after each robbery (Note that your total profit will not be checked again by the shareholders, i.e. your total profit may exceed M ).

Your target, professionally speaking, is to maximize the total profit of yourself after they finish robbing the banks according to your plan. Be careful of the annoying shareholders in the company!

Input
The input consists of several test cases. The first line of input gives the number of test cases T (T<=5).

For each test case:
The first line consists of four integers N, Q, K(1<=N<=1000, 1<=Q<=20, 1<=K<=50) and M (1<=M<=106).
The following K lines describe the property of banks, where the ith line contains ei, Ai, Bi, Ci(1<=ei<=Q, 1<=Ai, Bi, Ci<=109) in order.

Output
For each test case, output the maximum profits you can obtain in a line.

Sample Input
1
80 10 1 1000000
1 988123 894129 102939

Sample Output
999996

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

3
c++程序逻辑错误,求解!
2
来自计算机菜鸟的提问 :c语言中void怎么用?求解求解。求师傅
1
用c语言求解这个数学问题
2
求解一个概率方面的问题,用C语言来写:
4
c语言程序题,求解到底哪里有问题
0
矩阵三角形延展占用的行列坐标构图的问题,如何利用C语言的方式求解的?
0
RP问题的概率的联合分布律求解,采用的是C语言的思路的相关的做法
0
棋盘图案的二进制的一个编码的问题的求解过程,运用 C语言编程的具体做法
0
基数进行开平方运算的一个数字问题的求解?用C编程语言如何实现的
0
数列的倍增的一个算法题目的求解的过程,如何利用C语言的计算的编程?
0
因数的比率问题的求解,采用C编程语言的一个实现方式的探究
0
旅行者的问题的求解方式,运用C语言的编程技术怎么解决的
0
棋盘上的舞蹈的问题的求解,运用C语言的编程的方式怎么解决的
0
数组移动转换的问题的求解方式,怎么利用C语言算法的实现
0
数列的翻转表的一个算法的问题的求解,用C语言的程序编写怎么实现的啊
0
一次遍历求解不同数组的最大匹配,怎么利用C语言的程序的设计来实现的
0
循环队列的旋转的一个算法问题怎么利用C语言的程序的编写来求解的
0
信号的干涉的一个算法问题,怎么用C程序的设计的语言来求解的呢
0
一个rank的分类的一个算法的问题,用了C语言的程序的设计怎么求解的
0
路线的折叠的一个算法的问题怎么实现求解,用C程序的设计的语言的方式