codeforces712D Memory and Scores(접두어 및 최적화 dp)

1499 단어 codeforcesDP
제목:
두 사람이 취수 게임을 하는데 첫 번째 사람의 점수는 처음에 a이고 두 번째 점수는 처음에 b이다. 다음에 t라운드에서 두 사람이 [-k,k] 범위 내의 정수를 선택하여 자신의 점수에 넣고 몇 가지 상황을 구하여 t라운드가 끝난 후에 a의 점수가 b보다 높게 한다.(1 ≤ a, b ≤ 100, 1 ≤ k ≤ 1000, 1 ≤ t ≤ 100)
주요 사항:
처음에는 dp라고 생각하지 못했는데 실제로는 dp[i][j]로 제i라운드가 처음보다 j점을 많이 받는 방안수를 나타낼 수 있기 때문에 처음에는 a, b가 영향을 주지 않는다.-k는 마이너스가 나오기 때문에 아예 [-k,k]를 [0,2k]로 바꾸고 마지막에도 영향을 주지 않는다.상태 이동 방정식은 매우 간단하다. dp[i][j]=sum(dp[i-1][j-k....j+k]), 이렇게 상태량은 (2*k*t)*t이고 최대는 2e7이기 때문에 상태 이동은 반드시 O(1)이어야 하기 때문에 접두사와 유지보수를 사용한다.마지막으로 계산 결과는 첫 번째 사람의 j를 두루 훑어보고 두 번째 사람의 j차(a-b-1)를 구하는 방안의 수를 곱하기 때문에 이 단계도 접두사와 최적화를 사용할 수 있음을 주의한다.
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const ll N = 210000;//        j    
const ll mod = 1e9 + 7;
ll dp[110][N], sum[N];

int main()
{
	ll a, b, k, t;
	cin >> a >> b >> k >> t;
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	for (ll i = 1; i <= t; i++)
	{
		for (ll j = 0; j < N; j++)
			sum[j] = ((j ? sum[j - 1] : 0) + dp[i-1][j])%mod;//     
		for(ll j=0;j= 0 ? sum[j - 2 * k - 1] : 0) + mod) % mod;//  2*k       
	}
	ll ans = 0;
	for (ll i = 0; i < N; i++)//          
		sum[i] = ((i ? sum[i - 1] : 0) + dp[t][i])%mod;
	for (ll i = 0; i <= 2 * k*t; i++)//           
		ans = (ans + dp[t][i] * (i + a - b - 1 >= 0 ? sum[i+a-b-1] : 0) % mod) % mod;
	cout << ans << endl;
	return 0;
}
Laravel, Vue 3 및 Tailwind를 사용하여 프로젝트 템플릿 만들기 - 섹션 3
개발자 도구 오류 Debugging

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage