PKU演習問メモ(7/29) - simezi

夏休みの目標をここに宣言する。

PKU300問解く
TopCoder過去問Div1 Medium,Hardあわせて100問解く
赤コーダーになる
42.195Km泳ぐ（夏休みの累計で）
競技プログラミングで使うアルゴリズムのうち、日本語の解説がないものの解説をブログに纏める

1,2は最低量。達成するつもり。3は1,2の動機付け。4は単に運動不足なので。

No.	問題名	問題の種類および解法	難易度
3459	Projects	動的計画法	★★☆☆☆
3616	Milking Time	動的計画法	★★☆☆☆

3459 Projects

問題概要

事業のプロジェクトがm個ある。これらに、最大で合計n人の人員を割り当てて、得られる利益の期待値を最大化したい。

人員一人当たりの人件費がsararyで与えられ（ただしプロジェクトが失敗した場合sararyは支払われない）、各プロジェクトが成功した場合の利益がprofit[i],失敗した場合の損失をpunishment[i]で与えられる。
また、i番目のプロジェクトに、人員をj人割り当てた場合のプロジェクトの成功確率はp[i][j]%で与えられる。

このとき、利益の期待値の最大値を求めよ。
ただし、n,m≦100を満たす。

解法

i番目のプロジェクトまで割り当てを終えて、人員がj人残っている時の期待値の最大値をdp[i][j]とする。
i+1番目のプロジェクトに人員を0人からj人割り当てることができ、その時の期待値はdp[i][j]を元に求められる。

以上の考えを元にして動的計画法をすれば解ける。

ソースコード

int m,n,s,p[100][101],re[100],pu[100];
ll dp[100][101];

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d%d%d",&m,&n,&s);
		rep(i,m)
		{
			p[i][0]=0;
			rep(j,n)scanf("%d",p[i]+j+1);
			scanf("%d%d",re+i,pu+i);
			
			fill_n(dp[i],n+1,-inf);
		}
		
		rep(i,n+1)dp[0][n-i]=p[0][i]*(re[0]-s*i)-(100-p[0][i])*pu[0];
		
		for(int i=1;i<m;i++)rep(j,n+1)
		if(dp[i-1][j]!=-inf)rep(k,j+1)
		{
			ll expect=p[i][k]*(re[i]-s*k)-(100-p[i][k])*pu[i];
			dp[i][j-k]=max(dp[i][j-k],dp[i-1][j]+expect);
		}
		ll ans=*max_element(dp[m-1],dp[m-1]+n+1);
		cout<<ans<<endl;
		
		bool f=1;
		for(int i=n;i>=0;i--)if(dp[m-1][i]==ans)
		{
			if(f)f=0;
			else cout<<" ";
			cout<<n-i;
		}
		cout<<endl;
	}
	return 0;
}

3616 Milking Time

問題概要

牛はM個の区間時間（starttime[i]からendtime[i]の間として与えられる）に、efficient[i]の量のミルクを出すことができる。牛がミルクを出し終えた後はRの時間だけ休まなければならない。
このとき、得ることの出来るミルクの最大の量を求めよ。

M≦1000を満たす。

解法

まずは区間の開始時間でソートする。
i番目の区間までに得られるミルクの量の最大値をdp[i]とすれば、
dp[i]=max{dp[j]|0≦j＜iかつ、endtime[j]+Rがstarttime[i]以下}+efficient[i]
の関係が成り立つ。

これを元に動的計画法をすればよい。

ソースコード

struct S{
	int st,ed,ef;
	bool operator<(const S &r)const{
		return st<r.st;
	}
};

int n,m,r;
S s[1000];
int dp[1000];

int main()
{
	scanf("%d%d%d",&n,&m,&r);
	rep(i,m)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		s[i].st=a; s[i].ed=b; s[i].ef=c;
	}
	sort(s,s+m);
	
	rep(i,m)
	{
		int mx=0;
		rep(j,i)if(s[j].ed+r<=s[i].st)mx=max(mx,dp[j]);
		dp[i]=s[i].ef+mx;
	}
	printf("%d\n",*max_element(dp,dp+m));
	
	return 0;
}