这样状压有问题吗?
查看原帖
这样状压有问题吗?
982518
sjwhsss楼主2024/8/18 23:53

rt,除了会MLE以外还有什么问题

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;
int s[maxn] , a[maxn] , dp[1<<maxn][maxn] , n , f[1<<maxn][maxn];
//dp:状态为S最后一次为第i题时时的最少时间    f:对应状态剩余的时间
int DP()
{
	memset(dp , 0x3f , sizeof(dp));
	memset(f , 0 , sizeof(f));
	int N = (1<<n) - 1 , ans = 0x3f3f3f3f;
	for (int i = 0; i < n; i++)dp[0][i]=0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (1<< j & i)
			{
				for (int k = 0; k < n; k++)
				{
					if (__builtin_popcount(i) > 1 && k == j)continue;
					if (1 << k & i)
					{
						if (__builtin_popcount(i) - 1 & 1)
						{
							if (dp[i][j] >= dp[i^1<<j][k] + (a[j] > f[i^1<<j][k] ? a[j] - f[i^1<<j][k] : a[j]))
							{
								dp[i][j] = dp[i^1<<j][k] + (a[j] > f[i^1<<j][k] ? a[j] - f[i^1<<j][k] : a[j]);
								if (a[j] - f[i^1<<j][k] > f[i][j]) f[i][j]=a[j] - f[i^1<<j][k];
							}
						}
						else 
						{
							if (dp[i][j] >= dp[i^1<<j][k] + a[j] - f[i^1<<j][k])
							{
								dp[i][j]=dp[i^1<<j][k] + a[j] - f[i^1<<j][k];
								if (a[j] - f[i^1<<j][k] > f[i][j])f[i][j] = a[j] - f[i^1<<j][k];
							}
						}
					}
					
				}
				
			}
		}
	}
	for (int i = 0; i < n; i++)ans=min(ans , dp[N][i]);
	return ans;
}
int main ()
{
	int ans = 0;
	for (int i = 0; i < 4; i++)scanf("%d" , &s[i]);
	for (int i = 0; i < 4; i++)
	{
		n = s[i];
		memset(a , 0 , sizeof(a));
		for (int j = 0; j < n; j++)scanf("%d" , &a[j]);
		ans += DP();
	}
	printf("%d" , ans);
	return 0;
}
2024/8/18 23:53
加载中...