POJ1742 Coins DP

1558 단어
제목:
n종의 동전을 주고, 각종ci개를 준다.1에서 m 범위 내에 액면가의 동전 조합이 몇 가지가 있느냐고 물었다.
아이디어:
bool dp[m]의 배열을 가져옵니다.true 는 찾을 수 있고 false 는 찾을 수 없습니다.
val[i]를 찾았을 때 1부터 i-1까지 최대치가 mx라고 가정하면 최소치가 분명히 0이다.
그래서 now=val[i]를 취하면 dp에 대한 영향 구간은 [now, mx+now]이다.
매거now<=j<=mx+now;
if(dp[j-now])dp[j]=true;
앞에서 i-1개가 액면가를 x로 구성할 수 있다면 i번째 동전을 넣으면 x+now라는 값을 구성할 수 있다는 뜻이다.
하지만 밤새도록 WA를 생각했지만 왜 그런지 모르겠어요.
discuss에 있는 데이터도 지나갔어요.그래도 와야 돼.
진심이 상하면 일단 놔두세요. 혹시 나중에 갑자기 여기 무슨 버그가 났는지 알고 돌아설지도 몰라요.
#include<iostream>
#include<algorithm>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
const int N=120005,M=100005;
int m,n;
int val[N];
int cot;
bool dp[M];
void solve()
{
	memset(dp,0,sizeof(dp));
	dp[0]=true;
	int now=val[1];
	int mx=now;
	dp[now]=true;
	for(int i=2;i<=n;i++)
	{
		now=val[i];
		mx+=now;
		mx=min(mx,m);
		for(int j=now;j<=mx;j++)
		{
			if(dp[j-now])
				dp[j]=true;
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++)
		if(dp[i])
			ans++;
	printf("%d
",ans); } int main() { while(scanf("%d%d",&n,&m),n+m) { int nn=n; memset(val,0,sizeof(val)); for(int i=1;i<=nn;i++) scanf("%d",val+i); for(int i=1;i<=nn;i++) { scanf("%d",&cot); int j=2; cot--; while(cot) { if(j<=cot) { val[++n]=j*val[i]; cot-=j; } else { val[++n]=cot*val[i]; break; } j<<=1; } } sort(val+1,val+n+1); solve(); } return 0; }

좋은 웹페이지 즐겨찾기