HDU 5009 Paint Pearls(西安网络赛C题) dp+离散化+优化
2024-08-30 10:38:34
转自:http://blog.csdn.net/accelerator_/article/details/39271751
吐血ac。。。
11668627 | 2014-09-16 22:15:24 | Accepted | 5009 | 1265MS | 1980K | 2290 B | G++ |
|
Paint PearlsTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1473 Accepted Submission(s): 466 Problem Description
Lee has a string of n pearls. In the beginning, all the pearls have no color. He plans to color the pearls to make it more fascinating. He drew his ideal pattern of the string on a paper and asks for your help.
In each operation, he selects some continuous pearls and all these pearls will be painted to their target colors. When he paints a string which has k different target colors, Lee will cost k2 points. Now, Lee wants to cost as few as possible to get his ideal string. You should tell him the minimal cost. Input
There are multiple test cases. Please process till EOF.
For each test case, the first line contains an integer n(1 ≤ n ≤ 5×104), indicating the number of pearls. The second line contains a1,a2,...,an (1 ≤ ai ≤ 109) indicating the target color of each pearl. Output
For each test case, output the minimal cost in a line.
Sample Input
3
1 3 3 10 3 4 2 4 4 2 4 3 2 2 Sample Output
2
7 Source
Recommend
|
转自:http://blog.csdn.net/accelerator_/article/details/39271751
题意:给定一个目标颜色,每次能选一个区间染色,染色的代价为这个区间不同颜色数的平方,问最小代价
思路:先预处理,把相同颜色的一段合并成一个点,然后把颜色离散化掉,然后进行dp,dp[i]表示染到第i个位置的代价,然后往后转移,转移的过程记录下不同个数,这样就可以转移了,注意加个剪枝,就是如果答案大于了dp[n]就不用往后继续转移了
哎,dp思路还是很混乱,有空还要把这题好好做做。。。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<string> #define N 50005
#define M 15
#define mod 10000007
#define p 10000007
#define mod2 100000000
#define ll long long
#define LL long long
#define maxi(a,b) (a)>(b)? (a) : (b)
#define mini(a,b) (a)<(b)? (a) : (b) using namespace std; int n,k,s;
int a[N];
int b[N];
map<int,int>c;
int vis[N];
int dp[N];
int cou;
vector<int>save; void ini()
{
//memset(vis,0,sizeof(vis));
memset(dp,0x3f3f3f3f,sizeof(dp));
c.clear();
k=;
int i;
scanf("%d",&a[]);
k=;
b[]=a[];
for(i=;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]!=a[i-]){
k++;
b[k]=a[i];
}
}
s=;
for(i=;i<=k;i++){
if(c[ b[i] ]==){
// vis[ b[i] ]=1;
s++;
c[ b[i] ]=s;
}
} for(i=;i<=k;i++){
b[i]=c[ b[i] ];
// dp[i]=i;
}
// for(i=1;i<=k;i++){
// printf(" i=%d b=%d\n",i,b[i]);
//} } void solve()
{
int i,j;
dp[]=;
dp[k]=k;
for(i=;i<k;i++){
cou=;
// vis[ b[i] ]=1;
//save.push_back(b[i]);
for(j=i+;j<=k;j++){
// if(cou*cou>=k) break;
if(vis[ b[j] ]== ){
vis[ b[j] ]=;
save.push_back(b[j]);
cou++;
}
if (dp[i] + cou * cou >= dp[k]) break;
// printf(" i=%d j=%d dpj=%d cou=%d dp=%d ",i,j,dp[j],cou,dp[i]+cou*cou);
dp[j]=min(dp[j],dp[i]+cou*cou);
// printf(" dpj=%d\n",dp[j]);
}
for(vector<int>::iterator it=save.begin();it!=save.end();it++){
vis[*it]=;
}
save.clear();
}
} void out()
{
//for(int i=1;i<=k;i++){
// printf(" i=%d dp=%d\n",i,dp[i]);
//}
printf("%d\n",dp[k]);
} int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
//scanf("%d",&T);
//for(int cnt=1;cnt<=T;cnt++)
// while(T--)
while(scanf("%d",&n)!=EOF)
{
ini();
solve();
out();
} return ;
}
最新文章
- Springboot搭建web项目
- jiajianhao
- [转]vb socket通信(TCP/UDP)一对一、多对一
- SQL*Loader之CASE5
- css3立体旋转
- javascript-XMLHttpRequest
- 安装LAMP
- PowerMock遇到的问题——4
- 清除HTML中的特殊字符
- sizeof运算符
- Understanding GC pauses in JVM, HotSpot&#39;s minor GC.
- J2SE知识点摘记(十一)
- 用websocket实现后台推送消息
- 洗礼灵魂,修炼python(3)--从一个简单的print代码揭露编码问题,运行原理和语法习惯
- 解决Windows和Linux使用npm打包js和css文件不同的问题
- Oracle DB Day02(SQL)
- 使用 AudioContext 播放音频 解决 谷歌禁止自动播放音频
- maven作用
- (后端)Spring Boot自定义错误页面,Whitelabel Error Page处理方式(转)
- Xstart Insatll And Usage