I used dp[901][8101] for dynamic programming,but I got TLE.Can anyone give me some hints?

Edited by author 22.10.2024 17:34

thx~

I have try many of my tests, but I don't know what is wrong in my code. What is test #2, please?

1 1 1
2 2 11
2 4 2
3 3 111
3 5 12
3 9 3
4 4 1111
4 6 112
4 8 22
4 10 13
4 16 4
5 5 11111
5 7 1112
5 9 122
5 11 113
5 13 23
5 17 14
5 25 5
6 6 111111
6 8 11112
6 10 1122
6 12 222
6 14 123
6 18 33
6 20 24
6 26 15
6 36 6

I keep getting WA2, but none of the threads posted here seem to help me: every example i found worked on my program, and i just can't see what's wrong with it. Can someone please tell me if they see anything that doesn't work within my program? Thank you in advance.
#define DM 8101
#define DN 901
#include <iostream>
#include <set>
#include <queue>
using namespace std;

int n, v, vp, s, sp, cf[DN][DM], dp[DN][DM];
multiset <int> ord;//ordering the elements
queue <int> q;//rebuild

void formare(int nrc, int car, int sum, int ptr)//no of digits, digit, sum, sumof squares
{
    if (nrc > 100 || (cf[sum][ptr] && cf[sum][ptr] <= nrc))
        return;
    cf[sum][ptr] = nrc;
    dp[sum][ptr] = car;
    for (int i = 9; i >= 1; --i)
        formare(nrc + 1, i, sum + i, ptr + i*i);
}

void realc(int s, int sp)
{
    if (!s || !sp || !dp[s][sp])
        return;
    q.push(dp[s][sp]);
    v+=dp[s][sp];
    vp+=dp[s][sp]*dp[s][sp];
    realc(s - dp[s][sp], sp - dp[s][sp]*dp[s][sp]);
}

int main()
{
    cin >> n;
    for (int i = 9; i >= 1; --i)
        formare(1, i, i, i*i);
    cf[0][0] = 1;
    dp[0][0] = 0;
    while (n--)
    {
        cin >> s >> sp;
        if (s > 900 || sp > 8100)
            cout << "No solution\n";
        else if (s == 0 && sp == 0)
            cout << "0\n";
        else
        {
            realc(s, sp);
            if (q.size() <= 100)
            {
                while (!q.empty())
                {
                    if (v == s && vp == sp)
                        ord.insert(q.front());
                    q.pop();
                }
                for (auto i:ord)
                    cout << i;
                ord.clear();
                if (v != s || vp != sp)
                    cout << "No solution";
                cout << '\n';
            }
            else
            {
                cout << "No solution\n";
                while (!q.empty())
                    q.pop();
            }
        }
        v = vp = 0;
    }
    return 0;
}

All the test cases given in this forum are working.But giving WA 1

my code is:
#include <stdio.h>
#include <string.h>
 int len[910][8110];
 int dig[910][8110];
 int num[110];

 int main(){
  int t,s1,s2,k,pt,i,j,l,temp;
  memset(len,0,sizeof(len));
  for(i=1;i<=900;i++){
      for(j=1;j<=8100;j++){
          for(k=1;k<=9;k++){
              if((i-k)<0||(j-k*k)<0)
                  break;
              else if((i-k)==0&&(j-k*k)==0){
                  len[i][j] = 1;
                  dig[i][j] = k;
              }
              else if(len[i-k][j-k*k]>0){
                  if(len[i-k][j-k*k]+1<len[i][j]||len[i][j]==0){
                      len[i][j] = len[i-k][j-k*k]+1;
                      dig[i][j] = k;
                  }
              }
              else
                  continue;
          }
      }
  }
  scanf("%d",&t);
  while(t--){
  scanf("%d %d",&s1,&s2);
  pt = 0;
  if(len[s1][s2]==0||len[s1][s2]>100)
      printf("No Solution");
  else{
        i=s1;
        j=s2;
      while((len[i][j]>=1)&&i>=1&&j>=1){
          l = dig[i][j];
          num[pt++] = l;
          i = i-l;
          l = l*l;
          j-=l;
      }
      for(i=0;i<pt;i++){
        for(j=i+1;j<pt;j++){
            if(num[i]>num[j]){
             temp=num[i];
             num[i]=num[j];
             num[j] = temp;
            }
        }
      }
      for(i=0;i<pt;i++)
          printf("%d",num[i]);
  }
  printf("\n");
  }
  return 0;
 }

WTF?! I have RE4(Access Violation). I don't understand why?

Samples:

1
201 405
Should be 99(2) + (3)

1
301 907
Should be 99(3) + (4)

1
448 2824
Should output something large, but the solution definitely exists :)

Edited by author 26.08.2016 07:23

I have WA 2. I don't understand why? Give me some tests please, which will help me understand my mistake.
Thank you.

I have WA4. I don't understand why? Give me some tests please, which will help me understand my mistake.
Thank you.

Instead of doing a lot of System.out.print, write all chars in a StringBuilder, and then print the StringBuilder once in the end.

if the number of digits is greater than 100,  should print "No solution"

3 arrays [8100*900] of byte
O<8100*900*9, DP

Edited by author 10.09.2009 18:56

Why when I allocated staticly globaly memory like this
char a[10005][10005] = {0};
char d[10005][10005] = {0};
I got MLE 4, but not MLE 1?

Edited by author 29.12.2011 01:34

Can anyone tell me how to use dynamic programming in this problem

Or could you send me your code to investigate?
kobchik83@list.ru

Mine quite straightforward realization works about 1 sec. and uses almost 60 megabytes of memory. Please, give an idea how to solve it more quickly...

i have +27 submites on it just because i forgot tests like that:
1
808 6464("No solution")

Edited by author 10.10.2009 04:16