[CQUOJ 21412] 软妹币！软妹币！软妹币！（数学+DP）

本文主要是介绍[CQUOJ 21412] 软妹币！软妹币！软妹币！（数学+DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CQUOJ - 21412
题意大致是，用若干不同的数中的某些数加减得到 1…n之间的所有数，需要的最少几个不同的数
赛上是找规律做的，虽然过了，但是感觉不太稳，赛后看了题解恍然大悟

首先有这样一个事实，如果有 3个数可以表示 1..13
那么对于小于 13的n，答案至多为 3
所以我们可以考虑，用 i个数能够构造出的最大的数是多少

设 dp[i]表示 i个数最大能表示 [1, dp[i]]
此时我想表示大于 dp[i]的数，就势必要加入一个大于 dp[i]的数，设为 x
则此时我可以额外表示 [x-dp[i], x+dp[i]]区间里的数，而这个区间可能和 [1, dp[i]]重合
为了使右端点最大，将 x不断向右移，直至 x-dp[i]=dp[i]+1，此时新增区间于原区间无公共点
所以 x=2*dp[i]+1，右端点为 3*dp[i]+1
所以加入 x后 i+1个数能表示 [1, 3*dp[i]+1]
转移方程：
1) dp[1]=1;
2) dp[i]=dp[i-1]*3+1

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
#define Pow2(a) a*a
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<0?(-a):a;}int N;
int dp[13];int main()
{dp[1]=1;for(int i=1; i<13; i++) dp[i]=dp[i-1]*3+1;while(~scanf("%d", &N)){for(int i=1; i<13; i++){if(dp[i]>=N){printf("%d\n", i);break;}}}return 0;
}