程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ2955 Interesting Dart Game 鴿巢原理優化 + 動規

ZOJ2955 Interesting Dart Game 鴿巢原理優化 + 動規

編輯：C++入門知識

看得出是一個以代價為1的背包，但是一開始不知道怎麼優化，不愧是學長啊，居然做出來了，後來看了一下他們的思路，他們是優化到了10000以後進行背包的，後來看了他們的思路自己有了新的想法，跟他們的優化不同，我對數組從小到大排序，然後利用鴿巢原理進行優化

在鴿巢原理的介紹裡面，有例題介紹：設a1,a2,a3,……am是正整數的序列，試證明至少存在正數k和l，1<=k<=l<=m,是的和ak+ak+1+……+al是m的倍數，接下來開始證明：

構造一個序列s1=a1,s2=a1+a2，……，sm=a1+a2+……+am,那麼會產生兩種可能：

1：若有一個sn是m的倍數，那麼定理成立：

2：假設上述的序列中沒有任何一個元素是m的倍數，令rh ≡ sh mod m;其中h=1,2,……,m;我們已知上面的所有項都非m的倍數，得到s1模m的余數是r1,s2模m的余數是r2,同理往下類推，r是一個余數序列，在這裡所有的余數都不為0，因為假設是不存在有m的倍數的，所以r序列的元素小於m，根據抽屜原理（鴿巢原理），m個余數在[1,m-]區間裡的取值至少存在一對rh,rl，並且滿足 rh=rk,即sh和sk滿足

sk ≡ sh mod m，那麼假設h>k，得到

sh-sk = (a1+a2+……+ah) - (a1+a2+……+ak)

sh - sk =ak+1 +ak+2 +……+ah ≡ 0 mod m（此處的k是序列a的下標）

證明到此結束；

本題利用到了鴿巢原理的一點：

一個數組 A1,A2,……AN從小到大，對於一個遠大於AN的數，按題目要求來的最優解中，小於AN的數的個數肯定是不會大於 AN的，所以可以先對AN*AN來進行優化，得到答案的一部分，剩余的再進行背包即可

總是做算法，不如來個陶冶情操的文章一篇： http://www.sanwen.net/subject/3628849/

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-8


//const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

int dp[10000 + 5];
int w[100 + 5];

void clear() {
	memset(dp,-1,sizeof(dp));
}

int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		clear();
		int n,m;
		scanf("%d %d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%d",&w[i]);
		sort(w + 1,w + n + 1);
		int tmp = m;
		int maxn = w[n] * w[n];
		int ans = 0;
		if(m >= maxn) {
			tmp = m%maxn;
			ans = (m - m%maxn)/w[n];
		}
		dp[0] = 0;
		for(int i=1;i<=n;i++) 
			for(int j=w[i];j